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

int SWAR(unsigned int i)
{
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

Хорошо, давайте пройдемся по коду построчно:

Строка 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 бит потребует добавления одного дополнительного шага сдвига / добавления / маски, поскольку число 256 больше не вписывается в 8-битный байт.

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

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

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

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

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

j0 = i - 2*j1    (5)

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