Получение количества старших 1 бит

Question

Учитывая число без знака, каков хороший (желательно быстрый) способ получения количества старших 1-бит?

Мне нужно это для вычисления числа CIDR из четырехточечной маски IPv4.

Примечание: я видел получение-числа-конечных-1-битов , поэтому я могу выполнить поиск на основе таблицы.

Примечание 2. Дажехотя я добавил пару языковых тегов, для меня речь идет об алгоритме, поэтому, если у вас есть хороший на другом языке, пожалуйста, не стесняйтесь писать.

Редактировать: on endian-ness .

Я только что обнаружил, что функция INET_ADDR и IN_ADDR структура хранит адрес IPv4 в формате с прямым порядком байтов, тогда какx86 имеет младший порядок байтов, и большинство процессоров, которые я использую, также имеют младший порядок байтов.
Итак, таблицы поиска для этого конкретного случая достаточно быстрые.
Но спасибо за другие ответы: они очень хорошо работают вболее распространенный случай.

- jeroen

Answer 1

Если вы инвертируете все биты, вы можете использовать алгоритм обнаружения ведущего (эквивалентный алгоритму log2);см. например http://www -graphics.stanford.edu / ~ seander / bithacks.html .Вы можете изменить некоторые из этих алгоритмов и пропустить этап инверсии.

Answer 2

Если вы специально не ищете теоретических улучшений в количестве шагов (то есть O (lg (n)) в количестве битов), я не думаю, что вы практически добьетесь гораздо больших успехов, чем поиск в таблице, и у вас все еще есть алгоритм, которыйportable.

Я бы рассчитывал с комфортом сканировать более 100 миллионов сетевых масок IPv4 на предмет лидирующих в секунду, используя простой поиск таблиц в одном потоке на современной машине (исключая работу по фактическому захвату сетевой маски IPv4).).Я не уверен, что выгоды от дальнейшего улучшения алгоритмов будут стоить какой-либо дополнительной сложности.

Answer 3

Если все биты равны 0 до 1, вы можете использовать инструкцию ассемблера BSF , она вернет индекс первого набора бит (не ноль), начиная с младшего бита, затем вы можете вычестьиз 32 и получите количество установленных битов.
В противном случае, если вам нужно искать из старшего бита, вы можете использовать NOT для инвертирования битов, а также использовать BSR сканировать от старшего бита до нуля.

Answer 4

Этот вопрос , хотя и не имеет отношения к делу, показывает некоторый код C для выполнения CTZ / CLZ (подсчет ведущих / конечных нулей).Если вы инвертировали (не поразрядно) свой ввод перед вызовом одного из них, вы можете получить количество ведущих / трейлинговых.