Алгоритму почти 70 лет, а он до сих пор живёт в ядре Linux.

В 1957 году Wilkes, Wheeler и Gill описали быстрый способ считать количество установленных битов в числе. Не циклом по одному биту, а через маски и арифметику сразу над группами битов.

Идея простая:

- сначала считаем биты парами
- потом группами по 4
- потом по байтам
- в конце умножение собирает сумму в старший байт

Если в процессоре нет инструкции POPCNT, Linux использует похожий подход в __sw_hweight64.

Красивый пример того, как старый битовый трюк пережил десятилетия и всё ещё работает в современном системном коде.

@linux_education