Как посчитать количество установленных бит в 32-битном целом числе?
https://stackoverflow.com/questions/109023
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
8 бит, представляющие число 7, выглядят следующим образом:
00000111
Устанавливаются три бита.
Каковы алгоритмы определения количества установленных бит в 32-битном целом числе?
Решение
Это известно как 'Вес Хэмминга', 'popcount' или 'боковое сложение'.
«Лучший» алгоритм действительно зависит от того, на каком процессоре вы работаете и каков ваш шаблон использования.
Некоторые процессоры имеют для этого одну встроенную инструкцию, а другие имеют параллельные инструкции, которые действуют на битовые векторы.Параллельные инструкции (например, 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 — это обычно использовать перетасовку переменных для параллельного поиска в таблице по 4 бита за раз для каждого байта.(4 бита индексируют таблицу из 16 записей, хранящуюся в векторном регистре).
На процессорах Intel аппаратная 64-битная инструкция popcnt может превосходить по производительности СССЭ3 PSHUFB бит-параллельная реализация примерно в 2 раза, но только если ваш компилятор все правильно понимает.В противном случае SSE может выйти существенно вперед.В новых версиях компиляторов учитывается popcnt ложная зависимость проблема в интеле.
Использованная литература:
https://graphics.stanford.edu/~seander/bithacks.html
https://en.wikipedia.org/wiki/Hamming_weight
http://gurmeet.net/puzzles/fast-bit-counting-routines/
http://aggregate.ee.engr.uky.edu/MAGIC/#Population%20Count%20(Ones%20Count)
Другие советы
Также рассмотрите встроенные функции ваших компиляторов.
Например, в компиляторе 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() вместо встроенного
Теоретически любой компилятор, который знает, как эффективно подсчитывать popcount для целевого процессора, должен предоставлять эту функциональность через ISO C++. std::bitset<>.На практике в некоторых случаях для некоторых целевых процессоров может быть лучше использовать бит-хак AND/shift/ADD.
Для целевых архитектур, где аппаратный popcount является необязательным расширением (например, x86), не все компиляторы имеют std::bitset который использует его, когда он доступен.Например, MSVC не имеет возможности включить popcnt поддержка во время компиляции и всегда использует поиск по таблице, даже с /Ox /arch:AVX (что подразумевает SSE4.2, хотя технически для этого предусмотрена отдельная функция). popcnt.)
Но, по крайней мере, вы получаете что-то портативное, которое работает везде, а с помощью gcc/clang с правильными целевыми параметрами вы получаете аппаратное обеспечение для архитектур, которые его поддерживают.
#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.
х86-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 версия аргумента):
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.Процессор — это то, что ставят в 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)
+-------------------------------+
Это один из тех вопросов, когда полезно знать свою микроархитектуру.Я только что рассчитал время для двух вариантов под gcc 4.3.3, скомпилированных с -O3, используя встроенные строки C++ для устранения накладных расходов на вызов функций, один миллиард итераций, сохраняя текущую сумму всех счетчиков, чтобы гарантировать, что компилятор не удаляет ничего важного, используя rdtsc для измерения времени ( точный тактовый цикл).
inline int pop2(unsigned x, unsigned 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;
x = x + (x >> 8);
y = y + (y >> 8);
x = x + (x >> 16);
y = y + (y >> 16);
return (x+y) & 0x000000FF;
}
Немодифицированный Hacker's Delight потребовал 12,2 гигацикла.Моя параллельная версия (считающая в два раза больше битов) работает на частоте 13,0 гигациклов.Всего прошло 10,5 с для обоих вместе на процессоре Core Duo с частотой 2,4 ГГц.25 гигациклов = чуть более 10 секунд на этой тактовой частоте, поэтому я уверен, что мои тайминги правильные.
Это связано с цепочками зависимостей инструкций, которые очень плохи для этого алгоритма.Я мог бы снова почти удвоить скорость, используя пару 64-битных регистров.На самом деле, если бы я поступил умно и добавил x+y немного раньше, я мог бы сократить некоторые сдвиги.64-битная версия с некоторыми небольшими изменениями вышла бы примерно равной, но снова считала бы в два раза больше битов.
Со 128-битными SIMD-регистрами это еще один фактор в два раза, а наборы инструкций SSE часто также имеют хитрые сокращения.
Нет причин делать код особенно прозрачным.Интерфейс прост, на алгоритм можно ссылаться в Интернете во многих местах, и он поддается комплексному модульному тестированию.Программист, который наткнется на него, возможно, даже чему-то научится.Эти битовые операции чрезвычайно естественны на машинном уровне.
Хорошо, я решил использовать измененную 64-битную версию.Для этого один sizeof(unsigned long) == 8
inline int pop2(unsigned long x, unsigned long 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;
x = x + y;
x = x + (x >> 8);
x = x + (x >> 16);
x = x + (x >> 32);
return x & 0xFF;
}
Это выглядит примерно правильно (хотя я не проверяю тщательно).Сейчас тайминги выходят на уровне 10,70 гигагерц/14,1 гигагерц.Это более позднее число составило 128 миллиардов бит и соответствует 5,9 с, затраченным на этой машине.Непараллельная версия немного ускоряется, потому что я работаю в 64-битном режиме, и 64-битные регистры ей нравятся немного лучше, чем 32-битные.
Посмотрим, есть ли здесь еще немного конвейерной обработки ООО.Это было немного сложнее, поэтому я действительно немного протестировал.Сумма каждого члена в отдельности равна 64, а вся сумма — 256.
inline int pop4(unsigned long x, unsigned long y,
unsigned long u, unsigned long v)
{
enum { m1 = 0x5555555555555555,
m2 = 0x3333333333333333,
m3 = 0x0F0F0F0F0F0F0F0F,
m4 = 0x000000FF000000FF };
x = x - ((x >> 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);
x = x + y;
u = u + v;
x = (x & m3) + ((x >> 4) & m3);
u = (u & m3) + ((u >> 4) & m3);
x = x + u;
x = x + (x >> 8);
x = x + (x >> 16);
x = x & m4;
x = x + (x >> 32);
return x & 0x000001FF;
}
На мгновение я был взволнован, но оказалось, что gcc проделывает встроенные трюки с -O3, хотя в некоторых тестах я не использую ключевое слово inline.Когда я позволил gcc пошалить, миллиард вызовов pop4() занял 12,56 гигациклов, но я решил, что это сворачивает аргументы в константные выражения.Более реалистичной цифрой является 19,6gc, что дает еще 30% ускорения.Мой тестовый цикл теперь выглядит следующим образом: я проверяю, что каждый аргумент достаточно различен, чтобы gcc не мог обмануть.
hitime b4 = rdtsc();
for (unsigned long 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 миллиардов бит.
Почему бы не итеративно разделить на 2?
count = 0
while n > 0
if (n % 2) == 1
count += 1
n /= 2
Я согласен, что это не самый быстрый, но «лучший» несколько двусмысленен.Я бы сказал, что «лучшее» должно иметь элемент ясности.
Битовая путаница в Hacker's Delight становится намного понятнее, когда вы записываете битовые комбинации.
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;
}
На первом этапе четные биты добавляются к нечетным, образуя сумму битов в каждых двух.На других шагах куски высокого порядка добавляются к кускам младшего, полностью удваивая размер блока, пока мы не получим окончательный счетчик, занимающий весь int.
Для золотой середины между 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;
}
Это не самое быстрое и лучшее решение, но я нашел на своем пути тот же вопрос и начал думать и думать.наконец я понял, что это можно сделать вот так, если подойти к задаче с математической стороны и нарисовать график, затем обнаружить, что это функция, имеющая некоторую периодическую часть, а затем осознать разницу между периодами...так вот:
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);
}
}
Это можно сделать в O(k), где k количество установленных битов.
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
Функцию, которую вы ищете, часто называют «боковая сумма» или «подсчет населения» двоичного числа.Кнут обсуждает это в предварительном выпуске 1A, стр. 11-12 (хотя в томе 2, 4.6.3-(7) была краткая ссылка).
А классический локус это статья Питера Вегнера «Техника счета единиц в двоичном компьютере» из журнала Коммуникации ACM, Том 3 (1960) Номер 5, стр. 322.Там он приводит два разных алгоритма: один оптимизирован для чисел, которые, как ожидается, будут «разреженными» (т. е. будут иметь небольшое количество единиц), а другой — для противоположного случая.
Несколько открытых вопросов: -
- Если число отрицательное, то?
- Если число равно 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
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;
}
я думаю Брайан Керниган метод тоже будет полезен...Он проходит столько итераций, сколько установлено битов.Таким образом, если у нас есть 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;
}
Язык программирования C, 2-е изд., опубликованный в 1988 году.(Брайан В.Керниган и Деннис М.Ричи) упоминает об этом в упражнении 2-9.19 апреля 2006 года Дон Кнут указал мне, что этот метод «впервые был опубликован Питером Вегнером в CACM 3 (1960), 322.(Также открыто независимо Дерриком Лемером и опубликовано в 1964 году в книге под редакцией Беккенбаха.)»
Я использую приведенный ниже код, который более интуитивно понятен.
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
Логика:n & (n-1) сбрасывает последний установленный бит n.
P.S.:Я знаю, что это не решение 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-битного значения может быть быстрее.
Примерно в 1990 году я написал макрос быстрого подсчета битов для RISC-машин.Он не использует расширенную арифметику (умножение, деление, %), выборку памяти (слишком медленную), переходы (слишком медленные), но предполагает, что процессор имеет 32-битный сдвиговый механизм (другими словами, >> 1 и >> 32 занимают одинаковое количество циклов.) Предполагается, что небольшие константы (такие как 6, 12, 24) ничего не требуют для загрузки в регистры или хранятся во временных файлах и повторно используются снова и снова.
С учетом этих предположений на большинстве RISC-машин он считает 32 бита примерно за 16 циклов/инструкций.Обратите внимание, что 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
поэтому, если я возьму первый столбец (A) выше, сдвину его вправо на 1 бит и вычту его из AB, я получу результат (CD).Расширение до 3 бит аналогично;Если хотите, вы можете проверить это с помощью логической таблицы из 8 строк, как у меня выше.
- Дон Гиллис
если вы используете 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 )
вы, конечно, можете расширить этот шаблон, чтобы использовать разные типы (даже автоматическое определение размера бита), но для ясности я сделал его простым.
редактировать:забыл упомянуть, что это хорошо, потому что это должен работать в любом компиляторе C++, и он, по сути, просто разворачивает ваш цикл за вас, если для количества бит используется постоянное значение (другими словами, я почти уверен, что это самый быстрый общий метод, который вы найдете)
Мне особенно нравится этот пример из файла состояния:
#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);
где n — число, единицы которого нужно посчитать.
проверьте также,
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];
}
Я всегда использую это в соревновательном программировании, его легко писать и он эффективен:
#include <bits/stdc++.h>
using namespace std;
int countOnes(int n) {
bitset<32> b(n);
return b.count();
}
Существует множество алгоритмов подсчета установленных битов;но я думаю, что лучший — тот, который быстрее!Подробности вы можете увидеть на этой странице:
Я предлагаю вот это:
Подсчет битов, установленных в 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.
Быстрое решение 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
};
}
Вот портативный модуль (ANSI-C), который может протестировать каждый из ваших алгоритмов на любой архитектуре.
Ваш процессор имеет 9-битные байты?Нет проблем :-) На данный момент он реализует 2 алгоритма: алгоритм K&R и побайтовую таблицу поиска.Таблица поиска работает в среднем в 3 раза быстрее, чем алгоритм K&R.Если кто-то сможет найти способ сделать портативным алгоритм «Хакерское наслаждение», не стесняйтесь добавить его.
#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_
/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );
/* List of available bitcount algorithms.
* onTheFly: Calculate the bitcount on demand.
*
* lookupTalbe: Uses a small lookup table to determine the bitcount. This
* method is on average 3 times as fast as onTheFly, but incurs a small
* upfront cost to initialize the lookup table on the first call.
*
* strategyCount is just a placeholder.
*/
enum strategy { onTheFly, lookupTable, strategyCount };
/* String represenations of the algorithm names */
extern const char *strategyNames[];
/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );
#endif
.
#include <limits.h>
#include "bitcount.h"
/* The number of entries needed in the table is equal to the number of unique
* values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;
static int _defaultBitCount( unsigned int val ) {
int count;
/* Starting with:
* 1100 - 1 == 1011, 1100 & 1011 == 1000
* 1000 - 1 == 0111, 1000 & 0111 == 0000
*/
for ( count = 0; val; ++count )
val &= val - 1;
return count;
}
/* Looks up each byte of the integer in a lookup table.
*
* The first time the function is called it initializes the lookup table.
*/
static int _tableBitCount( unsigned int val ) {
int bCount = 0;
if ( !_lookupTableInitialized ) {
unsigned int i;
for ( i = 0; i != UCHAR_MAX + 1; ++i )
_bitCountTable[i] =
( unsigned char )_defaultBitCount( i );
_lookupTableInitialized = 1;
}
for ( ; val; val >>= CHAR_BIT )
bCount += _bitCountTable[val & UCHAR_MAX];
return bCount;
}
static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;
const char *strategyNames[] = { "onTheFly", "lookupTable" };
void setStrategy( enum strategy s ) {
switch ( s ) {
case onTheFly:
_bitcount = _defaultBitCount;
break;
case lookupTable:
_bitcount = _tableBitCount;
break;
case strategyCount:
break;
}
}
/* Just a forwarding function which will call whichever version of the
* algorithm has been selected by the client
*/
int bitcount( unsigned int val ) {
return _bitcount( val );
}
#ifdef _BITCOUNT_EXE_
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* Use the same sequence of pseudo random numbers to benmark each Hamming
* Weight algorithm.
*/
void benchmark( int reps ) {
clock_t start, stop;
int i, j;
static const int iterations = 1000000;
for ( j = 0; j != strategyCount; ++j ) {
setStrategy( j );
srand( 257 );
start = clock( );
for ( i = 0; i != reps * iterations; ++i )
bitcount( rand( ) );
stop = clock( );
printf
( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
reps * iterations, strategyNames[j],
( double )( stop - start ) / CLOCKS_PER_SEC );
}
}
int main( void ) {
int option;
while ( 1 ) {
printf( "Menu Options\n"
"\t1.\tPrint the Hamming Weight of an Integer\n"
"\t2.\tBenchmark Hamming Weight implementations\n"
"\t3.\tExit ( or cntl-d )\n\n\t" );
if ( scanf( "%d", &option ) == EOF )
break;
switch ( option ) {
case 1:
printf( "Please enter the integer: " );
if ( scanf( "%d", &option ) != EOF )
printf
( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
option, option, bitcount( option ) );
break;
case 2:
printf
( "Please select number of reps ( in millions ): " );
if ( scanf( "%d", &option ) != EOF )
benchmark( option );
break;
case 3:
goto EXIT;
break;
default:
printf( "Invalid option\n" );
}
}
EXIT:
printf( "\n" );
return 0;
}
#endif
32-битная или нет?Я только что пришел с этим методом на Java после прочтения "пройти собеседование по программированию«4-е издание, упражнение 5.5 (глава 5:Битовые манипуляции).Если младший бит равен 1 приращению count, затем сдвиньте целое число вправо.
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
Я думаю, что это более интуитивно понятно, чем решения с константой 0x33333333, какими бы быстрыми они ни были.Это зависит от вашего определения «лучшего алгоритма».
