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