ПОНИМАНИЕ, как посчитать конечные нули для числа, используя побитовые операторы в C

Question

Примечание - Это НЕ дубликат этого вопроса - Подсчитать последовательные нулевые биты (завершающий) справа параллельно: объяснение? .Связанный вопрос имеет другой контекст, он задает только цель использования signed().НЕ помечайте этот вопрос как дубликат.

Я нашел способ получить число конечных нулей в числе.Мне показалось немного странным Стэнфордский университет. Напишите здесь , что дает следующее объяснение.

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);
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;

Почему это работает?У меня есть понимание того, как шестнадцатеричные числа представляются в виде двоичных и побитовых операторов, но я не могу понять интуицию, стоящую за этой работой?Какой рабочий механизм?

Answer 1

Код не работает (присутствует неопределенное поведение).Вот исправленная версия, которую также немного легче понять (и, вероятно, быстрее):

uint32_t v;  // 32-bit word input to count zero bits on right
unsigned c;  // c will be the number of zero bits on the right
if (v) {
    v &= -v; // keep rightmost set bit (the one that determines the answer) clear all others
    c = 0;
    if (v & 0xAAAAAAAAu) c |= 1; // binary 10..1010
    if (v & 0xCCCCCCCCu) c |= 2; // binary 1100..11001100
    if (v & 0xF0F0F0F0u) c |= 4;
    if (v & 0xFF00FF00u) c |= 8;
    if (v & 0xFFFF0000u) c |= 16;
}
else c = 32;

Как только мы знаем, что установлен только один бит, мы определяем один бит результата за раз, одновременно тестируявсе биты, где результат является нечетным, затем все биты, где результат имеет набор 2-х мест и т. д.

Исходный код работал в обратном порядке, начиная со всех битов набора результатов (после if (c) c--;), а затем определить, какие из них должны быть равны нулю, и очистить их.

Поскольку мы изучаем один бит вывода за раз, я думаю, что более понятно построить вывод с использованием битовых операций, а не арифметики.

Answer 2

Этот код (из сети) в основном C, хотя v &= -signed(v); не является корректным C. Цель состоит в том, чтобы он вел себя как v &= ~v + 1;

Во-первых, если v равно нулю,затем он остается нулевым после операции &, и все операторы if пропускаются, поэтому вы получаете 32.

В противном случае операция & (после исправления) очищает все биты влевосамого правого 1, поэтому в этот момент v содержит один 1 бит.Затем c уменьшается до 31, то есть все 1 бит в пределах возможного диапазона результатов.

Затем операторы if определяют его числовую позицию по одному биту за раз (один бит номера позиции, а неv), очищая биты, которые должны быть 0.

Answer 3

Код сначала преобразует v таким способом, который является полностью нулевым, за исключением самого левого, который остается.Затем он определяет положение этого первого.

Сначала давайте посмотрим, как мы подавляем все единицы, кроме самого левого.

Предположим, что k - это позиция самого левого в v.. v = (vn-1, vn-2, .. vk + 1,1,0, .. 0).

-v - число, добавленное к v, даст 0 (на самом деле это дает 2^ n, но бит 2 ^ n игнорируется, если мы сохраняем только n младших значащих бит).

Какое значение должно быть в -v, чтобы v + -v = 0?

• очевидно, что биты k-1..0 в -k должны быть равны 0, чтобы при добавлении к завершающим нулям в v они давали ноль.

• бит k долженбыть в 1. Добавленный к тому в vk, это даст ноль, и перенос в единицу в заказе k + 1

• бит k + 1 из -v будет добавлен к vk+1 и к переносу, сгенерированному на шаге k.Это должно быть логическое дополнение vk + 1.Таким образом, независимо от значения vk + 1, у нас будет 1 + 0 + 1, если vk + 1 = 0 (или 1 + 1 + 0, если vk + 1 = 1), и результат будет 0 в порядке k + 1 с переносомгенерируется в порядке k + 2.

• Это похоже на биты n-1..k + 2, и все они должны быть логическим дополнением соответствующего бита в v.

Следовательно, мы получаем известный результат, что для получения -v необходимо

• оставить без изменений все конечные нули v

• оставить без изменений самый левый из v

• дополнить все остальные биты.

Если мы вычислим v & -v, у нас есть

 v      vn-1  vn-2    ...  vk+1  1   0   0  ... 0
-v   & ~vn-1 ~vn-2    ... ~vk+1  1   0   0  ... 0
v&-v      0     0     ...    0   1   0   0  ... 0

Так что v & -v держит только самый левый в v.

Чтобы найти местоположение первого, посмотрите код:

if (v) c--;  // no 1 in result? -> 32 trailing zeros. 
             // Otherwise it will be in range c..0=31..0
if (v & 0x0000FFFF) c -= 16; // If there is a one in left most part of v  the range
                             //   of possible values for the location of this one
                             //   will be 15..0.
                             // Otherwise, range must 31..16
                             // remaining range is c..c-15 
if (v & 0x00FF00FF) c -= 8;  // if there is one in either byte 0 (c=15) or byte 2 (c=31), 
                             // the one is in the lower part of range.
                             // So we must substract 8 to boundaries of range.
                             // Other wise, the one is in the upper part.
                             // Possible range of positions of v is now c..c-7
if (v & 0x0F0F0F0F) c -= 4;  // do the same for the other bits.
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;