В 1957 году Wilkes, Wheeler и Gill описали быстрый способ считать количество установленных битов в числе. Не циклом по одному биту, а через маски и арифметику сразу над группами битов.
Идея простая:
- сначала считаем биты парами
- потом группами по 4
- потом по байтам
- в конце умножение собирает сумму в старший байт
Если в процессоре нет инструкции POPCNT, Linux использует похожий подход в
__sw_hweight64.Красивый пример того, как старый битовый трюк пережил десятилетия и всё ещё работает в современном системном коде.