Подсчитайте последовательные нулевые биты (трейлинг) справа параллельно: объяснение?
Рассматривать эта ссылка с сайта Bit Twiddling Hacks.
Для подсчета завершающих битов используется следующий алгоритм:
unsigned int v; // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v); /* THIS LINE */
if (v) c--;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;
Может кто-нибудь объяснить мне роль линии, отмеченной как /* THIS LINE */ и что более важно, возможно ли использовать только побитовые операции, чтобы избежать использования signed() ?
РЕДАКТИРОВАТЬ: Как заменить signed() арифметическими / логическими / побитовыми операциями?
Решение
v &= -signed(v) очистит все, кроме самого низкого установленного бита (1-бит) из v, то есть извлекает младший значащий 1 бит из v (впоследствии v станет числом со степенью 2). Например, для v=14 (1110)после этого имеем v=2 (0010),
Здесь, используя signed() потому что v unsigned и вы пытаетесь отрицать unsigned значение (дает ошибку компиляции с VS2012) (комментарий от JoelRondeau). Или вы получите предупреждение, как это: warning C4146: unary minus operator applied to unsigned type, result still unsigned (мой тест).
Другие решения
Выражение v &= -signed(v), является И число и отрицание этого числа самого. Таким образом, мы выполняем двоичное И над числом и дополнительным представлением числа двух
Следуя тому, что я понял из кода:
AND v с дополнением 2: — устанавливает все цифры после первой 1 справа налево
Пример: — v = 10101000, затем -v = ~ v + 1 (дополнение 1 плюс 1) =
01010111 + 1 = 01011000
v&-v = 10101000 & 01011000 = 00001000
Там нет простой побитовой операции, чтобы сделать -signed(v), Для сложения и вычитания требуются переносы, операции с битом X могут влиять на бит X + 1. Итак, требуется арифметика.
Но в основном, одинарный -x это просто бинарный 0-x, так что вы можете использовать стандартную арифметику, если у вас нет операции прямого отрицания.
detector