Программисты РФ
Алгоритму почти 70 лет, и он по-прежнему в ядре Linux.
В 1957 году Уилкс, Уиллер и Гилл предложили эффективный способ подсчёта установленных битов в числе, обходясь без циклов. Они использовали маски и арифметику для работы с группами битов.
Сначала считаются биты парами, затем группами по 4, потом — по байтам. В завершение умножение собирает сумму в старший байт.
Если в процессоре нет инструкции POPCNT, Linux применяет аналогичный метод в __sw_hweight64.
Этот пример показывает, как старый битовый трюк с годами не потерял актуальность в современном коде. Если у вас установлено приложение,
вы можете сразу перейти в канал