В 1957 году Дэвид Уилкс, Дэвид Уилер и Стэнли Гилл описали быстрый способ подсчёта количества установленных битов (popcount).
Вместо проверки каждого бита по отдельности алгоритм постепенно суммирует их:
• сначала попарно;
• затем группами по 4;
• потом по байтам;
• в конце получает итог одним умножением.
Сегодня современные процессоры обычно выполняют эту операцию аппаратной инструкцией POPCNT, но если её нет, используются программные реализации на основе той же идеи.
В .NET для этого есть BitOperations.PopCount(), а подобные алгоритмы до сих пор можно встретить в низкоуровневом системном коде.
📍 Навигация: Вакансии • Задачи • Собесы
🐸 Библиотека шарписта
#il_люминатор