Как POPCNT реализован на аппаратном уровне?

Question

Согласно http://www.agner.org/optimize/instruction_tables.pdf, POPCNT Инструкция (которая возвращает число установленных битов в 32-битном или 64-битном регистре) имеет пропускную способность 1 инструкция за такт на современных процессорах Intel и AMD. Это намного быстрее, чем любая программная реализация, которая требует нескольких инструкций ( Как посчитать количество установленных бит в 32-разрядном целом числе?).

Как POPCNT так эффективно реализован в оборудовании?

Answer 1

Есть патент на комбинированное popcnt, битовое сканирование вперед / назад:

US8214414 B2 - Комбинированный счетчик битов и логика детектора

Аннотация

Описан объединенный путь к данным для PopCount и BitScan. Аппаратная схема включает в себя дерево компрессоров, используемое для функции PopCount, которое повторно используется функцией BitScan (например, прямое сканирование битов (BSF) или обратное сканирование битов (BSR)). Логика селектора позволяет дереву компрессора работать с входным словом для операции PopCount или BitScan на основе инструкции микропроцессора. Входное слово кодируется, если выбрана операция BitScan. Дерево компрессора принимает входное слово, работает с битами так, как будто все биты имеют одинаковый уровень значимости (например, для N-битного входного слова входное слово обрабатывается как N однобитных входов). Результатом схемы дерева компрессора является двоичное значение, представляющее число, относящееся к выполненной операции (число установленных битов для PopCount или позиция бита первого установленного бита, обнаруженного при сканировании входного слова).