Как работает этот волшебный метод подсчета битов?

На самом деле это не учитывает установленные биты в 32-битном слове, поскольку результат по характеру оператора по модулю должен быть меньше 0xf (он же 15).

Во-первых, уделим особое внимание оператору по модулю. Почему 15? И почему мы маскируем самый младший бит в каждом кусочке?

Обратите внимание, что каждый младший значащий полубайт имеет значение 16^k для некоторого k. Обратите внимание, что 16 mod 15 равно 1, поэтому 16^k mod 15 равно 1 для любого неотрицательного целочисленного значения k.

Это удобно, поскольку означает, что 16^k1 + 16^k2 + ... + 16^kn = n mod 15.

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

Однако мы не хотим просто подсчитывать специально отформатированные биты в nybbles. Мы хотим подсчитать количество битов, установленных в произвольном значении. Хитрость заключается в том, чтобы поместить эти биты значения в эти специально отформатированные кусочки, перемещая биты. Окончательный порядок полубайтов не важен, пока мы можем переместить один бит значения в один полубайт. Теоретически, поскольку мы используем 64-битные значения для подсчета, мы можем сопоставить каждый бит в 16-битном значении с его собственным полубайтом, что дает всего 8_ битов, как раз в рамках нашего 64-битного разрешения. Однако обратите внимание, что поскольку мы используем модуль 15, любое значение с 15 или 16 установленными битами будет отображаться как 0 или 1 соответственно.

Теперь давайте сосредоточимся на странной константе: 0x200040008001ULL

Обратите внимание на то, какие биты установлены (где бит 0 — младший значащий бит): 0, 15, 30 и 45. Вы могли заметить, что они расположены через 15-битные интервалы. Это удобно, потому что для значений меньше 2^15 это умножение просто создает несколько смещенных копий значения в 64-битном слове. Но когда значения становятся равными или большими, чем 2^15, копии начинают аддитивно перекрываться, что больше не полезно для подсчета битов. Это нормально, потому что с этой операцией по модулю мы все равно не можем надежно подсчитать до 15 бит информации. (Однако, если результат операции по модулю равен 0, мы знаем, что либо все биты, либо ни один из них не установлены, опять же предполагая, что мы получаем только значения меньше 2^15.)

Итак, мы переместили копии нашего 15-битного числа в наш 64-битный регистр. Второй шаг заключается в том, что маска извлекает только младшие биты каждого полубайта. Поскольку младший значащий бит каждого полубайта эквивалентен 1 (mod 15), оператор по модулю эффективно подсчитывает количество младших значащих битов, установленных в полубайтах.

Единственная оставшаяся деталь — убедиться, что каждый бит в нашем 15-битном числе попадет в слот младшего значащего полубайта ровно один раз.

Давайте проверим:

The first bit set, 0, doesn't shift the value at all, giving our value bits 0 through 14.
This places value value bits 0, 4, 8, and 12 in a least significant nybble bit slot.

The second bit set, 15, gives our value bits 15 through 29.
This places our value bits 1, 5, 9, and 13 in bits 16, 20, 24, and 28.

The third bit set, 30, gives our value bits 30 through 44.
This places our value bits 2, 6, 10, and 14 in bits 32, 36, 40, and 44.

Finally, the forth bit set, 45, gives our value bits 45 through 59.
This places our value bits 3, 7, 11, and 15 in bits 48, 52, 56, and 60.

Bits accounted for:
0, 4, 8,  and 12
1, 5, 9,  and 13
2, 6, 10, and 14
3, 7, 11, and 15

Легко визуально убедиться, что это отображает 16 бит. Однако обратите внимание, что маска на самом деле состоит из 15 1, а не 16. Таким образом, бит, помещенный в последний полубайт (начиная с 60-го бита, представляющего 15-й бит нашего значения, старший бит 16-битного значения), эффективно игнорируется.

На этом вся техника завершена:

1. Используйте умножение, чтобы преобразовать каждый бит в наименее значащий полубайтовый бит.
2. Используйте маску, чтобы выбрать только нужные полубайтовые биты.
3. Обратите внимание, что младший полубайтовый бит эквивалентен 1 (mod 15).
4. Следовательно, (mod 15) просто сложит эти биты вместе... до набора 14 бит.