8 битов, представляющих число 7, выглядят так:
00000111
Три бита установлены.
Какие существуют алгоритмы для определения количества установленных бит в 32-битном целом числе?
algorithm
binary
bit-manipulation
hammingweight
iec10967
Мэтт Хауэллс
источник
источник
Ответы:
Это известно как « Вес Хэмминга », «Попконт» или «Боковое дополнение».
«Лучший» алгоритм действительно зависит от того, на каком процессоре вы находитесь и какова ваша схема использования.
Некоторые процессоры имеют одну встроенную инструкцию для этого, а другие имеют параллельные инструкции, которые действуют на битовые векторы. Параллельные инструкции (например, x86
popcnt
на процессорах, где они поддерживаются) будут почти наверняка самыми быстрыми. Некоторые другие архитектуры могут иметь медленную инструкцию, реализованную с помощью микрокодированного цикла, который проверяет бит за цикл ( требуется цитирование ).Предварительно заполненный метод поиска в таблице может быть очень быстрым, если ваш ЦП имеет большой кэш и / или вы выполняете много этих инструкций в узком цикле. Однако он может пострадать из-за «пропуска кэша», когда ЦП должен извлечь часть таблицы из основной памяти. (Посмотрите каждый байт отдельно, чтобы таблица была маленькой.)
Если вы знаете, что ваши байты будут в основном 0 или 1, то есть очень эффективные алгоритмы для этих сценариев.
Я считаю, что очень хорошим алгоритмом общего назначения является следующий, известный как «параллельный» или «алгоритм SWAR переменной точности». Я выразил это на C-подобном псевдо-языке, вам может потребоваться настроить его для работы с конкретным языком (например, используя uint32_t для C ++ и >>> в Java):
Для JavaScript: принуждать к целому числу с
|0
для выполнения: изменение первой линииi = (i|0) - ((i >> 1) & 0x55555555);
Это лучший вариант поведения из всех рассмотренных алгоритмов в наихудшем случае, поэтому он будет эффективно работать с любым шаблоном использования или значениями, которые вы выбрасываете.
Как работает этот SWAR Bithack:
Первый шаг - это оптимизированная версия маскирования, чтобы изолировать нечетные / четные биты, сдвинуть их в линию и добавить. Это эффективно делает 16 отдельных сложений в 2-битных аккумуляторах ( SWAR = SIMD в регистре A ). Как
(i & 0x55555555) + ((i>>1) & 0x55555555)
.Следующий шаг берет нечетные / четные восемь из этих 16-кратных 2-разрядных аккумуляторов и добавляет их снова, производя 8-кратные 4-разрядные суммы.
i - ...
Оптимизация не представляется возможным в этот раз , так это просто маскировать до / после сдвига. Использование одной и той же0x33...
константы оба раза вместо0xccc...
сдвига является хорошей вещью при компиляции для ISA, которым нужно отдельно создавать 32-битные константы в регистрах.Последний шаг сдвига и добавления
(i + (i >> 4)) & 0x0F0F0F0F
расширяется до 4х 8-битных аккумуляторов. Маскируется после добавления вместо прежнего, поскольку максимальное значение в любом 4-битном аккумуляторе равно4
, если были установлены все 4 бита соответствующих входных битов. 4 + 4 = 8, который все еще умещается в 4 бита, поэтому перенос между полубайтовыми элементами невозможенi + (i >> 4)
.Пока что это просто нормальная SIMD с использованием методов SWAR с несколькими умными оптимизациями. Продолжение с тем же шаблоном еще 2 шага может увеличить до 2х 16-битных, чем до 1х 32-битных. Но есть более эффективный способ на машинах с быстрым аппаратным умножением:
Как только у нас будет достаточно «элементов», умножение на магическую константу может сложить все элементы в верхний элемент . В этом случае байтовые элементы. Умножение осуществляется путем сдвига влево и сложения, поэтому умножение
x * 0x01010101
результатов вx + (x<<8) + (x<<16) + (x<<24)
. Наши 8-битные элементы достаточно широки (и содержат достаточно малое количество отсчетов), что не приводит к переносу в эти верхние 8 бит.64-разрядная версия этого может делать 8x 8-разрядных элементов в 64-разрядном целом числе с множителем 0x0101010101010101 и извлекать старший байт с помощью
>>56
. Так что никаких дополнительных шагов не требуется, только более широкие константы. Это то, что GCC использует в__builtin_popcountll
системах x86, когда аппаратнаяpopcnt
инструкция не включена. Если вы можете использовать для этого встроенные или встроенные функции, сделайте это, чтобы дать компилятору возможность выполнить оптимизацию под конкретные цели.С полной SIMD для более широких векторов (например, считая весь массив)
Этот алгоритм побитового SWAR может распараллеливаться для одновременного выполнения в нескольких векторных элементах, а не в одном целочисленном регистре, для ускорения на процессорах с SIMD, но без использования команды popcount. (Например, код x86-64, который должен работать на любом процессоре, а не только на Nehalem или более поздней.)
Однако лучший способ использования векторных инструкций для popcount обычно заключается в использовании переменной-shuffle для поиска в таблице 4 битов одновременно для каждого байта параллельно. (4 бита индексируют таблицу из 16 записей, содержащуюся в векторном регистре).
На процессорах Intel аппаратная 64-битная команда popcnt может превзойти параллельную реализацию SSSE3
PSHUFB
примерно в 2 раза, но только если ваш компилятор все делает правильно . В противном случае SSE может выйти значительно вперед. Более новые версии компилятора знают о проблеме ложной зависимости popcnt от Intel .Ссылки:
источник
unsigned int
, чтобы легко показать, что он свободен от каких-либо знаковых битовых осложнений. Также былоuint32_t
бы безопаснее, как, например, вы получаете то, что ожидаете на всех платформах?>>
определяется реализацией для отрицательных значений. Аргумент должен быть изменен (или приведен) наunsigned
, и, поскольку код является 32-битным, его, вероятно, следует использоватьuint32_t
.Также рассмотрите встроенные функции ваших компиляторов.
Например, на компиляторе GNU вы можете просто использовать:
В худшем случае компилятор сгенерирует вызов функции. В лучшем случае компилятор выдаст команду процессора, чтобы выполнить ту же работу быстрее.
Встроенные функции GCC работают даже на нескольких платформах. Popcount станет основной в архитектуре x86, так что имеет смысл начать использовать встроенный сейчас. Другие архитектуры имеют популярность годами.
На x86 вы можете сказать компилятору, что он может предполагать поддержку
popcnt
инструкций с помощью-mpopcnt
или-msse4.2
включать векторные инструкции, которые были добавлены в том же поколении. См. Параметры GCC x86 .-march=nehalem
(или-march=
любой процессор, который вы хотите, чтобы ваш код принимал и настраивал) может быть хорошим выбором. Запуск полученного двоичного файла на старом процессоре приведет к ошибке недопустимой инструкции.Чтобы оптимизировать двоичные файлы для машины, на которой вы их собираете, используйте
-march=native
(с gcc, clang или ICC).MSVC предоставляет встроенную функцию для
popcnt
инструкции x86 , но в отличие от gcc, она действительно является встроенной для инструкции по оборудованию и требует аппаратной поддержки.Использование
std::bitset<>::count()
вместо встроенногоТеоретически, любой компилятор, который знает, как эффективно выполнять подсчет для целевого процессора, должен предоставлять эту функциональность через ISO C ++
std::bitset<>
. На практике для некоторых целевых процессоров вам может быть лучше использовать битовый хакерский / AND / Shift / ADD в некоторых случаях.Для целевых архитектур, где аппаратный popcount является необязательным расширением (например, x86), не у всех компиляторов есть такой,
std::bitset
который использует его при его наличии. Например, MSVC не имеет возможности включитьpopcnt
поддержку во время компиляции и всегда использует поиск в таблице , даже с/Ox /arch:AVX
(что подразумевает SSE4.2, хотя технически есть отдельный бит функции дляpopcnt
.)Но, по крайней мере, вы получаете что-то переносимое, которое работает везде, а с gcc / clang с правильными целевыми параметрами вы получаете аппаратный popcount для архитектур, которые его поддерживают.
Смотрите asm из gcc, clang, icc и MSVC в проводнике компилятора Godbolt.
x86-64
gcc -O3 -std=gnu++11 -mpopcnt
испускает это:Выдает PowerPC64
gcc -O3 -std=gnu++11
(дляint
версии arg):Этот источник вообще не специфичен для x86 или GNU, но компилируется только для x86 с помощью gcc / clang / icc.
Также обратите внимание, что запасной вариант gcc для архитектур без единой инструкции popcount - это поиск по байтам за раз. Это не удивительно для ARM, например .
источник
std::bitset::count
. после встраивания это компилируется в один__builtin_popcount
вызов.На мой взгляд, «лучшее» решение - это то, которое может быть прочитано другим программистом (или первым программистом два года спустя) без обильных комментариев. Возможно, вы захотите самое быстрое или умное решение, которое некоторые уже предоставили, но я предпочитаю удобство чтения в любое время.
Если вам нужна большая скорость (и при условии, что вы хорошо ее документируете, чтобы помочь своим преемникам), вы можете использовать поиск по таблице:
Хотя они полагаются на определенные размеры типов данных, поэтому они не настолько переносимы. Но, поскольку многие оптимизации производительности в любом случае не переносимы, это может и не быть проблемой. Если вам нужна мобильность, я бы остановился на удобочитаемом решении.
источник
if ((value & 1) == 1) { count++; }
наcount += value & 1
?От восторга хакера, с. 66, рис. 5-2
Выполняется в ~ 20-ти инструкции (зависит от арки), без ветвления.
Восторг Хакер это восхитительно! Настоятельно рекомендуется.
источник
Integer.bitCount(int)
использует ту же самую точную реализацию.pop
вместоpopulation_count
(илиpop_cnt
если у вас должно быть сокращение). @MarcoBolis Я предполагаю, что это будет справедливо для всех версий Java, но официально это будет зависеть от реализации :)Я думаю, что самый быстрый способ - без использования таблиц поиска и popcount - заключается в следующем. Он считает установленные биты всего за 12 операций.
Это работает, потому что вы можете подсчитать общее количество установленных бит, разделив их на две половины, посчитав количество установленных бит в обеих половинах, а затем сложив их. Также известен как
Divide and Conquer
парадигма. Давайте вдаваться в подробности ..Число битов в двух битах может быть
0b00
,0b01
или0b10
. Давайте попробуем разобраться с этим на 2 битах ..Это то, что требовалось: последний столбец показывает количество установленных бит в каждой двухбитной паре. Если двухбитное число
>= 2 (0b10)
тогдаand
производит0b01
, иначе это производит0b00
.Это утверждение должно быть легко понять. После первой операции у нас есть счетчик установленных битов на каждые два бита, теперь мы суммируем это количество на каждые 4 бита.
Затем мы суммируем приведенный выше результат, давая нам общее количество установленных бит в 4 битах. Последнее утверждение самое хитрое.
Давайте разберемся с этим дальше ...
Это похоже на второе утверждение; вместо этого мы считаем установленные биты группами по 4. Из-за наших предыдущих операций мы знаем, что в каждом куске есть количество установленных битов. Давайте посмотрим пример. Предположим, у нас есть байт
0b01000010
. Это означает, что у первого полубайта установлены 4 бита, а у второго - 2 бита. Теперь мы добавим эти кусочки вместе.Он дает нам количество установленных бит в байте в первом куске,
0b01100010
и поэтому мы маскируем последние четыре байта всех байтов в номере (отбрасывая их).Теперь каждый байт содержит количество установленных битов. Нам нужно сложить их все вместе. Хитрость заключается в том, чтобы умножить результат, на
0b10101010
который имеет интересное свойство. Если наше число имеет четыре байта,A B C D
это приведет к новому числу с этими байтамиA+B+C+D B+C+D C+D D
. Для 4-байтового номера может быть установлено максимум 32 бита, которые могут быть представлены как0b00100000
.Все, что нам сейчас нужно, это первый байт, который имеет сумму всех установленных бит во всех байтах, и мы получаем это
>> 24
. Этот алгоритм был разработан для32 bit
слов, но его можно легко изменить для64 bit
слов.источник
c =
? Похоже, это должно быть устранено. Кроме того, предложите дополнительный набор A "(((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24", чтобы избежать некоторых классических предупреждений.popcount(int v)
и дляpopcount(unsigned v)
. Для переносимости, рассмотритеpopcount(uint32_t v)
, и т.д. Действительно как часть * 0x1010101.return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
нам не нужно считать буквы, чтобы увидеть, что вы на самом деле делаете (так как вы отбросили первую0
, я случайно подумал, что вы использовали неправильный (перевернутый) битовый шаблон в качестве маски - то есть, пока я не заметил, что есть только 7 букв, а не 8).Мне стало скучно, и я рассчитал миллиард итераций трех подходов. Компилятор gcc -O3. CPU - это то, что они вставили в MacBook Pro 1-го поколения.
Самый быстрый - 3,7 секунды:
Второе место занимает тот же код, но с поиском 4 байта вместо 2 полуслов. Это заняло около 5,5 секунд.
Третье место занимает подход «боковое сложение», который занял 8,6 секунды.
Четвертое место занимает __builtin_popcount () из GCC, за позорные 11 секунд.
Метод подсчета за один раз был медленнее, и мне стало скучно ждать его завершения.
Поэтому, если вы заботитесь о производительности превыше всего, используйте первый подход. Если вам не безразлично потратить 64 КБ ОЗУ, используйте второй подход. В противном случае используйте читаемый (но медленный) подход, основанный на одном бите.
Трудно придумать ситуацию, в которой вы захотите использовать сложный подход.
Изменить: Подобные результаты здесь .
источник
Если вы используете Java, встроенный метод
Integer.bitCount
сделает это.источник
Позвольте мне объяснить этот алгоритм.
Этот алгоритм основан на алгоритме «разделяй и властвуй». Предположим, что есть 8-битное целое число 213 (11010101 в двоичном виде), алгоритм работает так (каждый раз объединяя два соседних блока):
источник
Это один из тех вопросов, который помогает узнать вашу микроархитектуру. Я просто рассчитал два варианта в gcc 4.3.3, скомпилированных с -O3, используя встроенные в C ++ значения, чтобы исключить накладные расходы при вызове функции, один миллиард итераций, сохраняя текущую сумму всех подсчетов, чтобы гарантировать, что компилятор не удалит ничего важного, используя rdtsc для синхронизации ( тактовый цикл точный).
Неизменный Восторг Хакера занял 12,2 гигациклов. Моя параллельная версия (считая вдвое больше битов) работает в 13,0 гигациклов. Всего 10,5 с прошло для обоих вместе на 2,4 ГГц Core Duo. 25 гигациклов = чуть более 10 секунд на этой тактовой частоте, поэтому я уверен, что мои настройки правильные.
Это связано с цепочками зависимостей команд, что очень плохо для этого алгоритма. Я мог бы почти удвоить скорость снова, используя пару 64-битных регистров. На самом деле, если бы я был умным и добавил x + ya немного раньше, я мог бы сбрить некоторые смены. 64-битная версия с некоторыми небольшими изменениями получилась бы ровной, но снова посчитала вдвое больше битов.
С 128-битными регистрами SIMD, еще одним фактором два, и наборы инструкций SSE также часто имеют умные сокращения.
Нет причин для того, чтобы код был особенно прозрачным. Интерфейс прост, на алгоритм можно ссылаться онлайн во многих местах, и он поддается всестороннему модульному тестированию. Программист, который наткнется на это, может даже чему-то научиться. Эти битовые операции чрезвычайно естественны на уровне машины.
ОК, я решил протестировать 64-битную версию. Для этого один размер (без знака long) == 8
Это выглядит правильно (я не проверяю тщательно, хотя). Теперь время выходит на 10,70 гигациклов / 14,1 гигациклов. Это более позднее число составило 128 миллиардов битов и соответствует 5,9 с, прошедшим на этой машине. Непараллельная версия немного ускоряется, потому что я работаю в 64-битном режиме, и ей нравятся 64-битные регистры немного лучше, чем 32-битные.
Давайте посмотрим, будет ли здесь еще больше конвейерной обработки OOO. Это было немного сложнее, так что я немного протестировал. Каждое слагаемое суммирует до 64, все вместе - до 256.
На мгновение я был взволнован, но оказалось, что gcc играет трюки со встроенным ключом -O3, хотя я не использую ключевое слово inline в некоторых тестах. Когда я позволяю gcc играть трюки, миллиард вызовов pop4 () занимает 12,56 гигациклов, но я решил, что это сворачивание аргументов в виде константных выражений. Более реалистичное число кажется 19,6gc для еще 30% ускорения. Мой тестовый цикл теперь выглядит следующим образом, убедившись, что каждый аргумент достаточно различен, чтобы gcc не играл трюки.
256 миллиардов битов за 8,17 секунды. Работает до 1,02 с для 32 миллионов битов, как это было указано в 16-битной таблице поиска. Невозможно сравнить напрямую, потому что другой стенд не дает тактовой частоты, но выглядит так, будто я выплюнул сопли из 64-килобайтного настольного издания, что, во-первых, трагическое использование кэша L1.
Обновление: решил сделать очевидное и создать pop6 (), добавив еще четыре дублированных строки. Вышел на 22,8gc, 384 миллиардов битов, суммированных за 9,5 с. Так что есть еще 20% сейчас при 800 мс для 32 млрд бит.
источник
Почему бы итеративно не разделить на 2?
Я согласен, что это не самый быстрый, но «лучший» несколько двусмысленно. Я бы сказал, что «лучшее» должно иметь элемент ясности
источник
Бит-тредлинг от восторга Хакера становится намного понятнее, когда вы записываете битовые паттерны.
Первый шаг добавляет четные биты к нечетным битам, создавая сумму битов в каждых двух. Другие шаги добавляют чанки высокого порядка к чанам низкого порядка, удваивая размер чанка до тех пор, пока мы не получим окончательный счет, занимающий все целое.
источник
Для счастливого среднего между таблицей поиска 2 32 и повторением каждого бита индивидуально:
С http://ctips.pbwiki.com/CountBits
источник
Это можно сделать там
O(k)
, гдеk
установлено количество битов.источник
n &= (n-1)
форму.Это не самое быстрое или лучшее решение, но я нашел тот же вопрос на своем пути, и я начал думать и думать. наконец, я понял, что это можно сделать так, если вы берете задачу с математической стороны и рисуете график, затем вы обнаруживаете, что это функция, имеющая некоторую периодическую часть, и затем вы понимаете разницу между периодами ... так Ну вот:
источник
def f(i, d={0:lambda:0, 1:lambda:1, 2:lambda:1, 3:lambda:2}): return d.get(i, lambda: f(i//4) + f(i%4))()
Функцию, которую вы ищете, часто называют «суммой сбоку» или «счетчиком чисел» двоичного числа. Кнут обсуждает это в предисловии 1А, сс.11-12 (хотя в томе 2, 4.6.3- (7) была краткая ссылка).
« Locus classicus» - это статья Питера Вегнера «Методика подсчета в двоичном компьютере», из сообщения ACM , том 3 (1960), номер 5, стр. 322 . Там он приводит два разных алгоритма, один из которых оптимизирован для чисел, которые, как ожидается, будут «разреженными» (т. Е. Иметь небольшое количество единиц), а другой - для противоположного случая.
источник
источник
Несколько открытых вопросов: -
мы можем изменить алгоритм для поддержки отрицательного числа следующим образом:
Теперь, чтобы преодолеть вторую проблему, мы можем написать алгоритм вроде:
для полной ссылки см .:
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
источник
Я думаю, что метод Брайана Кернигана тоже будет полезен ... Он проходит столько итераций, сколько есть установленных битов. Так что, если у нас есть 32-битное слово с установленным старшим битом, оно будет проходить только один раз в цикле.
источник
Я использую приведенный ниже код, который является более интуитивным.
Логика: n & (n-1) сбрасывает последний установленный бит n.
PS: я знаю, что это не O (1) решение, хотя и интересное решение.
источник
O(ONE-BITS)
. Это действительно O (1), поскольку существует не более 32 однобитных.Что вы имеете в виду под «Лучшим алгоритмом»? Замкнутый код или застывший код? Ваш код выглядит очень элегантно и имеет постоянное время выполнения. Код тоже очень короткий.
Но если скорость является основным фактором, а не размером кода, то я думаю, что следующее может быть быстрее:
Я думаю, что это не будет быстрее для 64-битного значения, но 32-битное может быть быстрее.
источник
Я написал быстрый макрос для подсчета числа битов для машин RISC примерно в 1990 году. Он не использует расширенную арифметику (умножение, деление,%), выборки памяти (слишком медленные), ветвления (слишком медленные), но он предполагает, что ЦП имеет 32-разрядный бочкообразный сдвиг (другими словами, >> 1 и >> 32 занимают одинаковое количество циклов.) Предполагается, что небольшие константы (например, 6, 12, 24) ничего не стоят для загрузки в регистры или хранятся во временных и повторного использования снова и снова.
С этими допущениями он рассчитывает 32 бита в 16 циклах / инструкциях на большинстве машин RISC. Обратите внимание, что 15 инструкций / циклов близки к нижней границе числа циклов или инструкций, потому что кажется, что требуется по крайней мере 3 инструкции (маска, смещение, оператор), чтобы сократить количество добавлений пополам, поэтому log_2 (32) = 5, 5 x 3 = 15 инструкций - это квази-нижняя граница.
Вот секрет первого и самого сложного шага:
поэтому, если я возьму 1-й столбец (A) выше, сдвину его вправо на 1 бит и вычту его из AB, я получу вывод (CD). Расширение до 3 бит аналогично; если хотите, вы можете проверить это с помощью булевой таблицы с 8 строками, как у меня выше.
источник
если вы используете C ++, другой вариант - использовать метапрограммирование шаблона:
использование будет:
Конечно, вы могли бы расширить этот шаблон, чтобы использовать разные типы (даже автоматически определяемый размер битов), но для простоты я оставил его простым.
edit: забыл упомянуть, что это хорошо, потому что он должен работать в любом компиляторе C ++, и он просто развертывает ваш цикл для вас, если для подсчета битов используется постоянное значение (другими словами, я уверен, что это самый быстрый общий метод ты найдешь)
источник
constexpr
хотя.Мне особенно нравится этот пример из файла состояния:
Мне нравится это больше всего, потому что это так красиво!
источник
Java JDK1.5
Integer.bitCount (п);
где n - число, чьи 1 должны быть подсчитаны.
проверьте также,
источник
Я нашел реализацию подсчета битов в массиве с использованием инструкции SIMD (SSSE3 и AVX2). Он имеет в 2-2,5 раза лучшую производительность, чем если бы он использовал встроенную функцию __popcnt64.
Версия SSSE3:
Версия AVX2:
источник
Я всегда использую это в конкурентном программировании, и это легко написать и эффективно:
источник
Есть много алгоритмов для подсчета установленных битов; но я думаю, что лучший - быстрее! Вы можете увидеть подробности на этой странице:
Бит Тиддлинг Хаки
Я предлагаю это:
Подсчет битов, установленных в 14, 24 или 32-битных словах с использованием 64-битных инструкций
Этот метод требует 64-битный процессор с быстрым модулем разделения для эффективности. Первый вариант занимает всего 3 операции; второй вариант занимает 10; а третий вариант занимает 15.
источник
Быстрое решение C # с использованием предварительно рассчитанной таблицы байтовых битов с разветвлением на входной размер.
источник
(0xe994 >>(k*2))&3
, без доступа к памяти ...Вот портативный модуль (ANSI-C), который может тестировать каждый из ваших алгоритмов на любой архитектуре.
Ваш процессор имеет 9-битные байты? Нет проблем :-) На данный момент он реализует 2 алгоритма, алгоритм K & R и таблицу побайтного поиска. Таблица поиска в среднем в 3 раза быстрее алгоритма K & R. Если кто-то может придумать, как сделать алгоритм «Хакерского восторга» переносимым, смело добавляйте его.
,
источник
что вы можете сделать, это
логика, лежащая в основе этого, состоит в том, что биты n-1 инвертированы из крайнего правого установленного бита n. если n = 6, т.е. 110, то 5 равно 101, биты инвертируются из крайнего правого установленного бита n. так что если мы и эти два мы сделаем самый правый бит 0 в каждой итерации и всегда перейдем к следующему крайнему правому установленному биту. Считаем установленный бит. Наихудшая временная сложность будет O (logn), когда каждый бит установлен.
источник