Как этот алгоритм подсчитывает количество заданных битов в 32-битном целочисленном?

Ответ 1

ОК, пропустите код по строкам:

Строка 1:

i = i - ((i >> 1) & 0x55555555);

Прежде всего, значение константы 0x55555555 заключается в том, что, написанное с использованием стиля Java/GCC двоичной литеральной литературы),

0x55555555 = 0b01010101010101010101010101010101

То есть все его биты с нечетным номером (считая младший бит как бит 1 = нечетный) составляют 1, а все четные биты 0.

Выражение ((i >> 1) & 0x55555555), таким образом, смещает биты i справа на единицу, а затем устанавливает все четные биты в ноль. (Эквивалентно, мы могли бы сначала установить все нечетные биты i в ноль с помощью & 0xAAAAAAAA, а затем сдвинуть результат на один бит.) Для удобства позвольте этому промежуточному значению j.

Что происходит, когда мы вычитаем этот j из оригинала i? Хорошо, посмотрим, что произойдет, если i имеет только два бита:

    i           j         i - j
----------------------------------
0 = 0b00    0 = 0b00    0 = 0b00
1 = 0b01    0 = 0b00    1 = 0b01
2 = 0b10    1 = 0b01    1 = 0b01
3 = 0b11    1 = 0b01    2 = 0b10

Эй! Нам удалось подсчитать бит нашего двухбитового номера!

ОК, но что, если i установлено более двух битов? На самом деле, довольно легко проверить, что нижние два бита i - j по-прежнему будут указаны в таблице выше, и так будут третий и четвертый бит, а пятый и шестой бит и так далее. В частности:

• несмотря на >> 1, младшие два бита i - j не влияют на третий или более высокий бит i, поскольку они будут скрыты из j с помощью & 0x55555555; и

• так как наименьшие два бита j никогда не могут иметь большее числовое значение, чем значение i, вычитание никогда не будет брать из третьего бита i: таким образом, самые низкие два бита i также не может влиять на третий или более высокий бит i - j.

Фактически, повторяя тот же аргумент, мы можем видеть, что вычисление на этой строке, по сути, применяет таблицу выше к каждому из 16 двухбитовых блоков в i параллельно. То есть, после выполнения этой строки, младшие два бита нового значения i теперь будут содержать количество бит, установленных между соответствующими битами в исходном значении i, и так будут следующие два бита и и так далее.

Строка 2:

i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

По сравнению с первой строкой, это довольно просто. Во-первых, обратите внимание, что

0x33333333 = 0b00110011001100110011001100110011

Таким образом, i & 0x33333333 принимает рассчитанные выше двухбитовые подсчеты и выбрасывает каждую вторую из них, а (i >> 2) & 0x33333333 делает то же самое после смещения i на два бита. Затем мы добавляем результаты вместе.

Таким образом, в действительности, что делает эта строка, берут битсочетания младших двух и двух младших битов исходного ввода, вычисленные на предыдущей строке, и складывают их вместе, чтобы дать битконты самых низких четырех бит ввода. И, опять же, он делает это параллельно для всех 8 четырехбитовых блоков (= шестнадцатеричных цифр) ввода.

Строка 3:

return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;

Хорошо, что здесь происходит?

Ну, во-первых, (i + (i >> 4)) & 0x0F0F0F0F делает то же самое, что и предыдущая строка, за исключением того, что он добавляет соседние четырехбитовые бит-таблицы вместе, чтобы дать биткоматы каждого восьмибитового блока (то есть байта) ввода. (Здесь, в отличие от предыдущей строки, мы можем уйти с перемещением & вне добавления, так как мы знаем, что восьмибитовый бит-бит никогда не может превышать 8 и, следовательно, будет помещаться внутри четырех бит без переполнения.)

Теперь у нас есть 32-разрядное число, состоящее из четырех 8-битных байтов, каждый байт содержит число 1 бит в этом байте исходного ввода. (Позвольте называть эти байты A, B, C и D.) Итак, что происходит, когда мы умножаем это значение (назовем его k) на 0x01010101?

Ну, так как 0x01010101 = (1 << 24) + (1 << 16) + (1 << 8) + 1, мы имеем:

k * 0x01010101 = (k << 24) + (k << 16) + (k << 8) + k

Таким образом, старший байт результата заканчивается суммой:

• его исходное значение, из-за термина k, плюс
• значение следующего нижнего байта, из-за члена k << 8, плюс
• значение второго младшего байта, из-за члена k << 16, плюс
• значение четвертого и младшего байтов из-за термина k << 24.

(В общем случае также могут быть перенесены из более низких байтов, но поскольку мы знаем, что значение каждого байта не превышает 8, мы знаем, что добавление никогда не переполнится и не создаст перенос.)

Таким образом, старший байт k * 0x01010101 заканчивается суммой битсочетаний всех байтов ввода, то есть общей бит-бит 32-битного входного номера. Окончательный >> 24 затем просто сдвигает это значение вниз от самого старшего байта до самого низкого.

Ps.Этот код можно было бы легко расширить до 64-битных целых чисел, просто изменив 0x01010101 на 0x0101010101010101 и >> 24 на >> 56. В самом деле, тот же метод будет работать даже для 128-битных целых чисел; Однако для 256 бит потребуется добавить один дополнительный шаг shift/add/mask, поскольку число 256 больше не подходит для 8-битного байта.

Ответ 2

Я предпочитаю это, это намного легче понять.

x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) &0x0000ffff);

Ответ 3

Это комментарий к ответу Иламари. Я поставил его как ответ из-за проблем с форматом:

Строка 1:

i = i - ((i >> 1) & 0x55555555);  // (1)

Эта строка получена из этой более понятной строки:

i = (i & 0x55555555) + ((i >> 1) & 0x55555555);  // (2)

Если мы будем называть

i = input value
j0 = i & 0x55555555
j1 = (i >> 1) & 0x55555555
k = output value

Мы можем переписать (1) и (2), чтобы упростить объяснение:

k =  i - j1; // (3)
k = j0 + j1; // (4)

Мы хотим показать, что (3) можно получить из (4).

i можно записать как добавление четных и нечетных битов (считая младший бит как бит 1 = нечетный):

i = iodd + ieven =
  = (i & 0x55555555) + (i & 0xAAAAAAAA) =
  = (i & modd) + (i & meven)

Так как маска meven очищает последний бит i, последнее равенство можно записать следующим образом:

i = (i & modd) + ((i >> 1) & modd) << 1 =
  = j0 + 2*j1

То есть:

j0 = i - 2*j1    (5)

Наконец, заменив (5) на (4), получим (3):

k = j0 + j1 = i - 2*j1 + j1 = i - j1