Цитирование кода для вычисления целочисленного абсолютного значения (абс) без ветвления из http://graphics.stanford.edu/~seander/bithacks.html:
int v; // we want to find the absolute value of v
unsigned int r; // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v + mask) ^ mask;
Запатентованная вариация:
r = (v ^ mask) - mask;
Что такое CHAR_BIT и как его использовать?
Вы должны знать, что этот код зависит от определенного поведением поведения правильного битового сдвига по подписанным типам. gcc promises, чтобы всегда давать разумное поведение (расшифровка знакового бита), но ISO C позволяет реализовать нулевое заполнение верхних бит.
Один из способов решения этой проблемы:
#ifdef HAVE_SIGN_EXTENDING_BITSHIFT
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
#else
int const mask = -((unsigned)v >> sizeof(int) * CHAR_BIT - 1);
#endif
Ваши Makefile или config.h и т.д. могут определять HAVE_SIGN_EXTENDING_BITSHIFT во время сборки в зависимости от вашей платформы.
CHAR_BIT - количество бит в char. В наши дни почти все архитектуры используют 8 бит на байт, но это не всегда так. Некоторые старые машины имели 7-битный байт.
Его можно найти в <limits.h>
Попытка ответить как на явный вопрос (что такое CHAR_BIT), так и на неявный вопрос (как это работает) в исходном вопросе.
A char в C и С++ представляет собой наименьшую единицу памяти, которую программа C может адресовать *
CHAR_BIT в C и С++ представляет количество бит в char. Он должен быть не менее 8 из-за других требований к типу char. Практически на всех современных компьютерах общего назначения это ровно 8, но некоторые исторические или специализированные системы могут иметь более высокие значения.
Java не имеет эквивалентности CHAR_BIT или sizeof, в этом нет необходимости, так как все примитивные типы в Java являются фиксированным размером, а внутренняя структура объектов непрозрачна для программиста. Если вы переводите этот код на Java, вы можете просто заменить "sizeof (int) * CHAR_BIT - 1" на фиксированное значение 31.
В этом конкретном коде он используется для вычисления числа бит в int. Имейте в виду, что в этом расчете предполагается, что тип int не содержит битов заполнения.
Предполагая, что ваш компилятор решит подписать расширение на сдвиги бит подписанных чисел и предположив, что ваша система использует представление дополнений 2s для отрицательных чисел, это означает, что "MASK" будет 0 для положительного или нулевого значения и -1 для отрицательного значения.
Чтобы свести на нет два дополнительных номера, нам нужно выполнить побитовое, а затем добавить один. Равномерно мы можем вычесть одно, а затем поразрядное отрицать его.
Снова предполагая, что представление двойного дополнения -1 представлено всеми, поэтому эксклюзивное или с -1 равносильно побитовому отрицанию.
Поэтому, когда v равно нулю, число остается в покое, когда v является одним, оно отрицается.
Что-то нужно знать о том, что подписанное переполнение в C и С++ - это поведение undefined. Поэтому использование этой реализации ABS на самом отрицательном значении приводит к поведению undefined. Это можно устранить, добавив отливки таким образом, чтобы конечная строка программы оценивалась в unsigned int.
* Обычно это не носально, как наименьшая единица памяти, на которую может обращаться аппаратное обеспечение. Реализация может потенциально объединить несколько единиц аппаратно адресуемой памяти в один блок памяти с программной памятью или разделить один блок аппаратной адресной памяти на несколько блоков памяти с дополнительной памятью.