Как посчитать количество установленных бит в 32-битном целом числе?
8 битов, представляющих число 7, выглядят так:
00000111
Три бита установлены.
Какие существуют алгоритмы для определения количества установленных бит в 32-битном целом числе?
67 ответов
Это известно как " вес Хэмминга ", "попконт" или "боковое сложение".
"Лучший" алгоритм действительно зависит от того, на каком процессоре вы находитесь и какова ваша модель использования.
Некоторые процессоры имеют одну встроенную инструкцию для этого, а другие имеют параллельные инструкции, которые действуют на битовые векторы. Параллельные инструкции (как в x86 popcnt на процессорах, где это поддерживается) почти наверняка будет самым быстрым. Некоторые другие архитектуры могут иметь медленную инструкцию, реализованную с помощью микрокодированного цикла, который проверяет бит за цикл (требуется цитирование).
Предварительно заполненный метод поиска в таблице может быть очень быстрым, если ваш ЦП имеет большой кэш и / или вы выполняете много этих инструкций в тесном цикле. Однако он может пострадать из-за "пропуска кэша", когда ЦП должен извлечь часть таблицы из основной памяти.
Если вы знаете, что ваши байты будут в основном 0 или 1, то есть очень эффективные алгоритмы для этих сценариев.
Я считаю, что очень хорошим алгоритмом общего назначения является следующий, известный как "параллельный" или "алгоритм SWAR переменной точности". Я выразил это на C-подобном псевдо-языке, вам может потребоваться настроить его для работы с конкретным языком (например, используя uint32_t для C++ и >>> в Java):
int numberOfSetBits(int i)
{
// Java: use >>> instead of >>
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
Это лучший вариант поведения из всех рассмотренных алгоритмов в наихудшем случае, поэтому он будет эффективно работать с любым шаблоном использования или значениями, которые вы выбрасываете.
Этот алгоритм побитового SWAR может распараллеливаться для одновременного выполнения в нескольких векторных элементах, а не в одном целочисленном регистре, для ускорения на процессорах с SIMD, но без использования команды popcount. (например, код x86-64, который должен запускаться на любом процессоре, а не только на Nehalem или более поздней.)
Тем не менее, лучший способ использовать векторные инструкции для popcount обычно заключается в использовании переменной-shuffle для поиска в таблице 4 битов одновременно для каждого байта параллельно. (4 бита индексируют таблицу из 16 записей, содержащуюся в векторном регистре).
На процессорах Intel аппаратная 64-битная команда popcnt может превзойти SSSE3 PSHUFB Битопараллельная реализация примерно в 2 раза, но только если ваш компилятор все делает правильно. В противном случае SSE может выйти значительно вперед. Более новые версии компилятора знают о проблеме ложной зависимости popcnt от Intel.
Рекомендации:
https://graphics.stanford.edu/~seander/bithacks.html
https://en.wikipedia.org/wiki/Hamming_weight
Также рассмотрите встроенные функции ваших компиляторов.
Например, на компиляторе GNU вы можете просто использовать:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
В худшем случае компилятор сгенерирует вызов функции. В лучшем случае компилятор выдаст команду процессора, чтобы выполнить ту же работу быстрее.
Встроенные функции GCC работают даже на нескольких платформах. Popcount станет основной в архитектуре x86, поэтому имеет смысл начать использовать встроенный сейчас. Другие архитектуры имеют популярность в течение многих лет.
На x86 вы можете сказать компилятору, что он может предполагать поддержку popcnt инструкция с -mpopcnt или же -msse4.2 также включить векторные инструкции, которые были добавлены в том же поколении. См. Параметры GCC x86. -march=nehalem (или же -march= любой процессор, который вы хотите, чтобы ваш код предполагал и настраивал), может быть хорошим выбором. Запуск полученного двоичного файла на старом процессоре приведет к ошибке недопустимой инструкции.
Чтобы оптимизировать двоичные файлы для машины, на которой вы их собираете, используйте -march=native (с gcc, clang или ICC).
MSVC предоставляет встроенную для x86 popcnt инструкция, но в отличие от 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 для архитектур, которые его поддерживают.
#include <bitset>
#include <limits>
#include <type_traits>
template<typename T>
//static inline // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value, unsigned >::type
popcount(T x)
{
static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BIT
constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
// std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03
static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");
typedef typename std::make_unsigned<T>::type UT; // probably not needed, bitset width chops after sign-extension
std::bitset<bitwidth> bs( static_cast<UT>(x) );
return bs.count();
}
Смотрите asm из gcc, clang, icc и MSVC в проводнике компилятора Godbolt.
x86-64 gcc -O3 -std=gnu++11 -mpopcnt испускает это:
unsigned test_short(short a) { return popcount(a); }
movzx eax, di # note zero-extension, not sign-extension
popcnt rax, rax
ret
unsigned test_int(int a) { return popcount(a); }
mov eax, edi
popcnt rax, rax
ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
xor eax, eax # gcc avoids false dependencies for Intel CPUs
popcnt rax, rdi
ret
PowerPC64 gcc -O3 -std=gnu++11 испускает (для int версия arg):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
Этот источник вообще не специфичен для x86 или GNU, но компилируется только для x86 с помощью gcc/clang/icc.
Также обратите внимание, что запасной вариант gcc для архитектур без единой инструкции popcount - это поиск по байтам за раз. Это не удивительно для ARM, например.
На мой взгляд, "лучшее" решение - это то, которое может быть прочитано другим программистом (или оригинальным программистом два года спустя) без обильных комментариев. Возможно, вы захотите самое быстрое или умное решение, которое некоторые уже предоставили, но я предпочитаю удобство чтения в любое время.
unsigned int bitCount (unsigned int value) {
unsigned int count = 0;
while (value > 0) { // until all bits are zero
if ((value & 1) == 1) // check lower bit
count++;
value >>= 1; // shift bits, removing lower bit
}
return count;
}
Если вам нужна большая скорость (и при условии, что вы хорошо ее документируете, чтобы помочь своим преемникам), вы можете использовать поиск по таблице:
// Lookup table for fast calculation of bits set in 8-bit unsigned char.
static unsigned char oneBitsInUChar[] = {
// 0 1 2 3 4 5 6 7 8 9 A B C D E F (<- n)
// =====================================================
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n
: : :
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn
};
// Function for fast calculation of bits set in 16-bit unsigned short.
unsigned char oneBitsInUShort (unsigned short x) {
return oneBitsInUChar [x >> 8]
+ oneBitsInUChar [x & 0xff];
}
// Function for fast calculation of bits set in 32-bit unsigned int.
unsigned char oneBitsInUInt (unsigned int x) {
return oneBitsInUShort (x >> 16)
+ oneBitsInUShort (x & 0xffff);
}
Хотя они полагаются на определенные размеры типов данных, поэтому они не настолько переносимы. Но, поскольку многие оптимизации производительности в любом случае не переносимы, это может и не быть проблемой. Если вам нужна мобильность, я бы остановился на удобочитаемом решении.
От восторга хакера, с. 66, рис. 5-2
int pop(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
Выполняется в ~20-ти инструкции (зависит от арки), без ветвления.
Восторг Хакера восхитителен! Настоятельно рекомендуется.
Я думаю, что самый быстрый способ - без использования таблиц поиска и popcount - заключается в следующем. Он считает установленные биты всего за 12 операций.
int popcount(int v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
Это работает, потому что вы можете подсчитать общее количество установленных бит, разделив их на две половины, посчитав количество установленных бит в обеих половинах, а затем сложив их. Также известен как Divide and Conquer парадигма. Давайте вдаваться в подробности..
v = v - ((v >> 1) & 0x55555555);
Количество битов в двух битах может быть 0b00, 0b01 или же 0b10, Давайте попробуем разобраться с этим на 2 битах..
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
Это то, что требовалось: последний столбец показывает количество установленных бит в каждой двухбитной паре. Если двухбитное число >= 2 (0b10) затем and производит 0b01 иначе он производит 0b00,
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
Это утверждение должно быть легко понять. После первой операции у нас есть счетчик установленных битов на каждые два бита, теперь мы суммируем это количество на каждые 4 бита.
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
Затем мы суммируем вышеприведенный результат, давая нам общее количество установленных бит в 4 битах. Последнее утверждение самое хитрое.
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
Давайте разберемся дальше...
v + (v >> 4)
Это похоже на второе утверждение; вместо этого мы считаем установленные биты в группах по 4. Из-за наших предыдущих операций мы знаем, что в каждом клеве есть количество установленных бит. Давайте посмотрим пример. Предположим, у нас есть байт 0b01000010, Это означает, что у первого полубайта установлены 4 бита, а у второго - 2 бита. Теперь мы добавим эти кусочки вместе.
0b01000010 + 0b01000000
Это дает нам количество установленных бит в байте, в первом клеве 0b01100010 и поэтому мы маскируем последние четыре байта всех байтов в числе (отбрасывая их).
0b01100010 & 0xF0 = 0b01100000
Теперь каждый байт содержит количество установленных битов. Нам нужно сложить их все вместе. Хитрость заключается в умножении результата на 0b10101010 который имеет интересное свойство. Если наш номер имеет четыре байта, A B C D, это приведет к новому числу с этими байтами A+B+C+D B+C+D C+D D, Для 4-байтового номера может быть установлено максимум 32 бита, которые могут быть представлены как 0b00100000,
Все, что нам сейчас нужно, это первый байт, который имеет сумму всех установленных бит во всех байтах, и мы получаем его >> 24, Этот алгоритм был разработан для 32 bit слова, но могут быть легко изменены для 64 bit слова.
Если вы используете Java, встроенный метод Integer.bitCount сделаю это.
Мне стало скучно, и я рассчитал миллиард итераций трех подходов. Компилятор gcc -O3. CPU - это то, что они вставили в MacBook Pro 1-го поколения.
Самый быстрый - 3,7 секунды:
static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}
Второе место занимает тот же код, но с поиском 4 байта вместо 2 полуслов. Это заняло около 5,5 секунд.
Третье место занимает подход "боковое сложение", который занял 8,6 секунды.
Четвертое место занимает __builtin_popcount () из GCC, за позорные 11 секунд.
Метод подсчета за один раз был медленнее, и мне надоело ждать его завершения.
Так что если вы заботитесь о производительности превыше всего, используйте первый подход. Если вам не безразлично тратить на него 64 КБ ОЗУ, используйте второй подход. В противном случае используйте читаемый (но медленный) подход, основанный на одном бите.
Трудно придумать ситуацию, в которой вы захотите использовать сложный подход.
Изменить: Подобные результаты здесь.
unsigned int count_bit(unsigned int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
return x;
}
Позвольте мне объяснить этот алгоритм.
Этот алгоритм основан на алгоритме "разделяй и властвуй". Предположим, что есть 8-битное целое число 213(11010101 в двоичном виде), алгоритм работает так (каждый раз объединяя два соседних блока):
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
Почему бы итеративно не разделить на 2?
count = 0
пока n > 0
if (n % 2) == 1
считать += 1
н /= 2
Я согласен, что это не самый быстрый, но "лучший" несколько двусмысленно. Я бы сказал, что "лучшее" должно иметь элемент ясности
Это один из тех вопросов, который помогает узнать вашу микроархитектуру. Я только что рассчитал два варианта в gcc 4.3.3, скомпилированных с -O3, используя встроенные в C++ значения, чтобы исключить накладные расходы при вызове функции, один миллиард итераций, сохраняя текущую сумму всех подсчетов, чтобы компилятор не удалил ничего важного, используя rdtsc для синхронизации (тактовый цикл точен).
встроенный int pop2(без знака x, без знака y)
{
x = x - ((x >> 1) и 0x55555555);
y = y - ((y >> 1) и 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F;
х = х + (х >> 8);
у = у + (у >> 8);
х = х + (х >> 16);
у = у + (у >> 16);
return (x + y) & 0x000000FF;
}
Неизменный Восторг Хакера занял 12,2 гигациклов. Моя параллельная версия (считая вдвое больше битов) работает в 13,0 гигациклов. Всего 10,5 с прошло для обоих вместе на 2,4 ГГц Core Duo. 25 гигациклов = чуть более 10 секунд на этой тактовой частоте, поэтому я уверен, что мои настройки правильные.
Это связано с цепочками зависимостей команд, что очень плохо для этого алгоритма. Я мог бы почти удвоить скорость снова, используя пару 64-битных регистров. На самом деле, если бы я был умным и добавил x+y a немного раньше, я мог бы сбрить некоторые смены. 64-битная версия с некоторыми небольшими изменениями получилась бы ровной, но снова посчитала вдвое больше битов.
С 128-битными регистрами SIMD, еще одним фактором два, и наборы инструкций SSE также часто имеют умные сокращения.
Нет причин для того, чтобы код был особенно прозрачным. Интерфейс прост, на алгоритм можно ссылаться онлайн во многих местах, и он поддается всестороннему модульному тестированию. Программист, который натыкается на это, может даже чему-то научиться. Эти битовые операции чрезвычайно естественны на уровне машины.
ОК, я решил протестировать 64-битную версию. Для этого один размер (без знака long) == 8
встроенный int pop2(длинный без знака x, длинный без знака y)
{
x = x - ((x >> 1) и 0x5555555555555555);
y = y - ((y >> 1) и 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x >> 2) и 0x3333333333333333);
y = (y & 0x3333333333333333) + ((y >> 2) и 0x3333333333333333);
x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
х = х + у;
х = х + (х >> 8);
х = х + (х >> 16);
х = х + (х >> 32);
вернуть x & 0xFF;
}
Это выглядит правильно (хотя я не проверяю тщательно, хотя). Теперь время выходит на 10,70 гигациклов / 14,1 гигациклов. Это более позднее число составило 128 миллиардов битов и соответствует 5,9 с, прошедшим на этой машине. Непараллельная версия немного ускоряется, потому что я работаю в 64-битном режиме, и ей нравятся 64-битные регистры немного лучше, чем 32-битные.
Давайте посмотрим, будет ли здесь еще немного конвейерной обработки OOO. Это было немного сложнее, так что я немного протестировал. Каждый термин сам по себе равен 64, а все вместе - 256.
встроенный int pop4 (длинный без знака x, длинный без знака y,
unsigned long u, unsigned long v)
{
enum {m1 = 0x5555555555555555,
м2 = 0x3333333333333333,
m3 = 0x0F0F0F0F0F0F0F0F,
m4 = 0x000000FF000000FF};
х = х - ((х >> 1) & m1);
y = y - ((y >> 1) & m1);
u = u - ((u >> 1) & m1);
v = v - ((v >> 1) & m1);
x = (x & m2) + ((x >> 2) & m2);
y = (y & m2) + ((y >> 2) & m2);
u = (u & m2) + ((u >> 2) & m2);
v = (v & m2) + ((v >> 2) & m2);
х = х + у;
u = u + v;
x = (x & m3) + ((x >> 4) & m3);
u = (u & m3) + ((u >> 4) & m3);
х = х + и;
х = х + (х >> 8);
х = х + (х >> 16);
х = х & м4;
х = х + (х >> 32);
return x & 0x000001FF;
}
На мгновение я был взволнован, но оказалось, что gcc играет трюки со встроенным ключом -O3, хотя в некоторых тестах я не использую ключевое слово inline. Когда я позволяю gcc играть трюки, миллиард вызовов pop4 () занимает 12,56 гигациклов, но я решил, что это сворачивание аргументов в виде константных выражений. Более реалистичное число кажется 19,6gc для еще 30% ускорения. Мой тестовый цикл теперь выглядит следующим образом, убедившись, что каждый аргумент достаточно различен, чтобы gcc не играл трюки.
hitime b4 = rdtsc ();
для (длинная без знака i = 10L * 1000 * 1000 * 1000; i <11L * 1000 * 1000 * 1000; ++ i)
sum + = pop4 (i, i ^ 1, ~ i, i | 1);
hitime e4 = rdtsc ();
256 миллиардов битов за 8,17 секунды. Работает до 1,02 с для 32 миллионов битов, как в 16-битных таблицах. Непосредственно сравнивать нельзя, потому что другой стенд не дает тактовой частоты, но выглядит так, будто я выплюнул сопли из табличного издания 64 КБ, что, в первую очередь, является трагическим использованием кэша L1.
Обновление: решил сделать очевидное и создать pop6(), добавив еще четыре дублированных строки. Вышел на 22,8gc, 384 миллиардов битов, суммированных за 9,5 с. Так что есть еще 20% сейчас при 800 мс для 32 млрд бит.
Переплетение битов восторга Хакера становится намного понятнее, когда вы записываете битовые паттерны.
unsigned int bitCount(unsigned int x)
{
x = (((x >> 1) & 0b01010101010101010101010101010101)
+ x & 0b01010101010101010101010101010101);
x = (((x >> 2) & 0b00110011001100110011001100110011)
+ x & 0b00110011001100110011001100110011);
x = (((x >> 4) & 0b00001111000011110000111100001111)
+ x & 0b00001111000011110000111100001111);
x = (((x >> 8) & 0b00000000111111110000000011111111)
+ x & 0b00000000111111110000000011111111);
x = (((x >> 16)& 0b00000000000000001111111111111111)
+ x & 0b00000000000000001111111111111111);
return x;
}
Первый шаг добавляет четные биты к нечетным битам, производя сумму битов в каждых двух. Другие шаги добавляют чанки старшего порядка к чанам младшего разряда, удваивая размер чанка до тех пор, пока мы не получим окончательный счет, занимающий все целое.
Для счастливого среднего между таблицей поиска 232 и повторением каждого бита индивидуально:
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
Это можно сделать в O(k), где k количество установленных битов
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
Это не самое быстрое или лучшее решение, но я нашел тот же вопрос на своем пути, и я начал думать и думать. в конце концов я понял, что это можно сделать следующим образом, если вы возьмете задачу с математической стороны и нарисуете график, тогда вы обнаружите, что это функция, имеющая некоторую периодическую часть, и затем вы поймете разницу между периодами... так Ну вот:
unsigned int f(unsigned int x)
{
switch (x) {
case 0:
return 0;
case 1:
return 1;
case 2:
return 1;
case 3:
return 2;
default:
return f(x/4) + f(x%4);
}
}
Я думаю, что метод Брайана Кернигана тоже будет полезен... Он проходит столько же итераций, сколько и заданных битов. Так что если у нас есть 32-битное слово с установленным старшим битом, оно будет проходить только один раз в цикле.
int countSetBits(unsigned int n) {
unsigned int n; // count the number of bits set in n
unsigned int c; // c accumulates the total bits set in n
for (c=0;n>0;n=n&(n-1)) c++;
return c;
}
Опубликовано в 1988 году, язык программирования Си 2-е изд. (Брайан В. Керниган и Деннис М. Ричи) упоминает об этом в упражнении 2-9. 19 апреля 2006 г. Дон Кнут указал мне на то, что этот метод "впервые был опубликован Питером Вегнером в CACM 3 (1960), 322. (Также был открыт независимо Дерриком Лемером и опубликован в 1964 г. в книге, отредактированной Беккенбахом)".
Функция, которую вы ищете, часто называется "суммой сбоку" или "счетчиком чисел" двоичного числа. Кнут обсуждает это в предисловии 1А, сс.11-12 (хотя в томе 2, 4.6.3-(7) была краткая ссылка).
" Locus classicus" - статья Питера Вегнера "Методика подсчета в двоичном компьютере", из сообщений ACM, том 3 (1960), номер 5, стр. 322. Там он приводит два разных алгоритма, один из которых оптимизирован для чисел, которые, как ожидается, будут "разреженными" (т. Е. Иметь небольшое количество единиц), а другой - для противоположного случая.
private int get_bits_set(int v)
{
int c; // c accumulates the total bits set in v
for (c = 0; v>0; c++)
{
v &= v - 1; // clear the least significant bit set
}
return c;
}
Несколько открытых вопросов:-
- Если число отрицательное то?
- Если число равно 1024, то метод "итеративно разделить на 2" будет повторяться 10 раз.
мы можем изменить алгоритм для поддержки отрицательного числа следующим образом:
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
Теперь, чтобы преодолеть вторую проблему, мы можем написать алгоритм вроде:
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
для полной ссылки см.:
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
Я использую приведенный ниже код, который является более интуитивным.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
Логика: n & (n-1) сбрасывает последний установленный бит n.
PS: я знаю, что это не O(1) решение, хотя и интересное решение.
Что вы имеете в виду под "Лучшим алгоритмом"? Замкнутый код или застывший код? Ваш код выглядит очень элегантно и имеет постоянное время выполнения. Код тоже очень короткий.
Но если скорость является основным фактором, а не размером кода, то я думаю, что следующее может быть быстрее:
static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
static int bitCountOfByte( int value ){
return BIT_COUNT[ value & 0xFF ];
}
static int bitCountOfInt( int value ){
return bitCountOfByte( value )
+ bitCountOfByte( value >> 8 )
+ bitCountOfByte( value >> 16 )
+ bitCountOfByte( value >> 24 );
}
Я думаю, что это не будет быстрее для 64-битного значения, но 32-битное может быть быстрее.
Если вы используете C++, другой вариант - использовать метапрограммирование шаблона:
// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
// return the least significant bit plus the result of calling ourselves with
// .. the shifted value
return (val & 0x1) + countBits<BITS-1>(val >> 1);
}
// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
return val & 0x1;
}
использование будет:
// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )
// another byte (this returns 7)
countBits<8>( 254 )
// counting bits in a word/short (this returns 1)
countBits<16>( 256 )
Конечно, вы могли бы расширить этот шаблон, чтобы использовать разные типы (даже автоматически определяемый размер битов), но для простоты я оставил его простым.
edit: забыл упомянуть, что это хорошо, потому что он должен работать в любом компиляторе C++, и он просто развертывает ваш цикл для вас, если для подсчета битов используется постоянное значение (другими словами, я уверен, что это самый быстрый общий метод ты найдешь)
Что вы можете сделать, это
while(n){
n=n&(n-1);
count++;
}
логика, лежащая в основе этого, состоит в том, что биты n-1 инвертируются из крайнего правого установленного бита n. если n=6, т.е. 110, то 5 равно 101, биты инвертируются из крайнего правого установленного бита n. так что если мы и эти два мы сделаем самый правый бит 0 в каждой итерации и всегда перейдем к следующему крайнему правому установленному биту. Считаем установленный бит. Наихудшая временная сложность будет O(logn), когда каждый бит установлен.
Я написал быстрый макрос для подсчета числа битов для машин RISC примерно в 1990 году. Он не использует расширенную арифметику (умножение, деление, %), выборки памяти (слишком медленные), ветвления (слишком медленные), но он предполагает, что процессор имеет 32-разрядный бочкообразный сдвиг (другими словами, >> 1 и >> 32 занимают одинаковое количество циклов.) Предполагается, что небольшие константы (например, 6, 12, 24) ничего не стоят для загрузки в регистры или сохраняются во временных и повторного использования снова и снова.
С этими допущениями он рассчитывает 32 бита в 16 циклах / инструкциях на большинстве машин RISC. Обратите внимание, что 15 инструкций / циклов близки к нижней границе числа циклов или инструкций, потому что кажется, что требуется по крайней мере 3 инструкции (маска, сдвиг, оператор), чтобы сократить количество добавлений пополам, поэтому log_2(32) = 5, 5 x 3 = 15 инструкций - это квази-нижняя граница.
#define BitCount(X,Y) \
Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
Y = ((Y + (Y >> 3)) & 030707070707); \
Y = (Y + (Y >> 6)); \
Y = (Y + (Y >> 12) + (Y >> 24)) & 077;
Вот секрет первого и самого сложного шага:
input output
AB CD Note
00 00 = AB
01 01 = AB
10 01 = AB - (A >> 1) & 0x1
11 10 = AB - (A >> 1) & 0x1
поэтому, если я возьму 1-й столбец (A) выше, сдвину его вправо на 1 бит и вычту его из AB, я получу вывод (CD). Расширение до 3 бит аналогично; если хотите, вы можете проверить это с помощью булевой таблицы с 8 строками, как у меня выше.
- Дон джиллис
C++20std::popcount
Следующее предложение было объединено http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html и должно добавить его в <bit> заголовок.
Я ожидаю, что использование будет как:
#include <bit>
#include <iostream>
int main() {
std::cout << std::popcount(0x55) << std::endl;
}
Я попробую, когда придет поддержка GCC, GCC 9.1.0 с g++-9 -std=c++2a все еще не поддерживает это.
Предложение говорит:
Заголовок:
<bit>namespace std { // 25.5.6, counting template<class T> constexpr int popcount(T x) noexcept;
а также:
template<class T> constexpr int popcount(T x) noexcept;Ограничения: T - целочисленный тип без знака (3.9.1 [basic.fundamental]).
Возвращает: число 1 бит в значении x.
std::rotl а также std::rotr были также добавлены для выполнения круговых вращений битов: Лучшие практики для операций кругового сдвига (вращения) в C++
Я всегда использую это в конкурентном программировании, и это легко написать и эффективно:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
Быстрое решение C# с использованием предварительно рассчитанной таблицы байтовых битов с разветвлением по входному размеру.
public static class BitCount
{
public static uint GetSetBitsCount(uint n)
{
var counts = BYTE_BIT_COUNTS;
return n <= 0xff ? counts[n]
: n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
: n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
: counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
}
public static readonly uint[] BYTE_BIT_COUNTS =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
}
Мне особенно нравится этот пример из файла состояния:
#define BITCOUNT (x) (((BX_ (x) + (BX_ (x) >> 4)) & 0x0F0F0F0F)% 255)
#define BX_ (x) ((x) - (((x) >> 1) и 0x77777777)
- (((x)>>2) и 0x33333333)
- (((x)>>3) и 0x11111111))Мне нравится это больше всего, потому что это так красиво!
Java JDK1.5
Integer.bitCount (п);
где n - число, чьи 1 должны быть подсчитаны.
проверьте также,
Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 times
n = 1;
for (int i = 0; i < 16; i++) {
n = Integer.rotateLeft(n, 1);
System.out.println(n);
}
Я нашел реализацию подсчета битов в массиве с использованием инструкции SIMD (SSSE3 и AVX2). Он имеет в 2-2,5 раза лучшую производительность, чем если бы он использовал встроенную функцию __popcnt64.
Версия SSSE3:
#include <smmintrin.h>
#include <stdint.h>
const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m128i _sum = _mm128_setzero_si128();
for (size_t i = 0; i < size; i += 16)
{
//load 16-byte vector
__m128i _src = _mm_loadu_si128((__m128i*)(src + i));
//get low 4 bit for every byte in vector
__m128i lo = _mm_and_si128(_src, F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
}
uint64_t sum[2];
_mm_storeu_si128((__m128i*)sum, _sum);
return sum[0] + sum[1];
}
Версия AVX2:
#include <immintrin.h>
#include <stdint.h>
const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m256i _sum = _mm256_setzero_si256();
for (size_t i = 0; i < size; i += 32)
{
//load 32-byte vector
__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
//get low 4 bit for every byte in vector
__m256i lo = _mm256_and_si256(_src, F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
}
uint64_t sum[4];
_mm256_storeu_si256((__m256i*)sum, _sum);
return sum[0] + sum[1] + sum[2] + sum[3];
}
Есть много алгоритмов для подсчета установленных битов; но я думаю, что лучший - быстрее! Вы можете увидеть подробности на этой странице:
Я предлагаю это:
Подсчет битов, установленных в 14, 24 или 32-битных словах с использованием 64-битных инструкций
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;
// option 2, for at most 24-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;
// option 3, for at most 32-bit values in v:
c = ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
Для этого метода требуется 64-битный процессор с быстрым разделением по модулю. Первый вариант занимает всего 3 операции; второй вариант занимает 10; а третий вариант занимает 15.