Как посчитать количество установленных бит в 32-битном целом числе?

По-моему, "лучшим" решением является то, которое может быть считано другим программистом (или исходным программистом два года спустя) без обильных комментариев. Можно хотеть самое быстрое или самое умное решение, которое некоторые уже предоставили, но я предпочитаю удобочитаемость по уму любое время.

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);
}

, Хотя они полагаются на определенные размеры типа данных, таким образом, они не то, что портативны. Но, так как много оптимизаций производительности не являются портативными так или иначе, который не может быть проблемой. Если бы Вы хотите мобильность, я придерживался бы читаемого решения.

От Восхищения Хакера, p. 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-выхода (зависимый дуги), никакое ветвление.

Восхищение Хакера восхитительно! Наиболее рекомендуемый.

Если Вы, окажется, будете использовать Java, встроенный метод Integer.bitCount сделает это.

Я скучал и синхронизировал миллиард повторений трех подходов. Компилятор является gcc-O3. ЦП - то, что они вставляют 1-го генерала MacBook Pro.

Самый Быстрый следующее, в 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 секунд.

Четвертое место переходит к GCC's __ builtin_popcount () в позорных 11 секунды.

подсчет one-bit-at-a-time подход был waaaay медленнее, и я скучал ожидания его для завершения.

Поэтому, если Вы заботитесь о производительности прежде всего остального тогда, используют первый подход. Если Вы заботитесь, но недостаточно потратить 64 КБ RAM на нем, используйте второй подход. Иначе используйте читаемое (но медленный) one-bit-at-a-time подход.

трудно думать о ситуации, где Вы хотели бы использовать подход битового жонглирования.

Редактирование: Подобные результаты здесь .

Почему не многократно делятся на 2?

count = 0
while n > 0
  if (n % 2) == 1
    count += 1
  n /= 2  

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

Для золотой середины между 2 <глоток> 32 таблица поиска и выполняющий итерации через каждый бит индивидуально:

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;
}

От http://ctips.pbwiki.com/CountBits

Функция, которую Вы ищете, часто вызывается "поперечная сумма" или "количество населения" двоичного числа. Knuth обсуждает его в предварительной грозди 1 А, pp11-12 (хотя была краткая ссылка в Объеме 2, 4.6.3-(7).)

местоположение classicus является статьей "A Technique for Counting Ones in a Binary Computer" Peter Wegner, от Связь ACM, Объем 3 (1960) Номер 5, страница 322 . Он дает два различных алгоритма там, один оптимизированный для чисел ожидал быть "редким" (т.е. иметь небольшое количество) и один для противоположного случая.

Также рассмотрите встроенные функции своих компиляторов.

На компиляторе GNU, например, можно просто использовать:

int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);

В худшем случае компилятор генерирует вызов к функции. В лучшем случае компилятор испустит инструкцию по CPU сделать то же задание быстрее.

GCC intrinsics даже работают через несколько платформ. Popcount станет господствующей тенденцией в x86 архитектуре, таким образом, будет иметь смысл начинать использовать внутреннее теперь. Другая архитектура имеет popcount в течение многих лет.

<час>

На x86, можно сказать компилятору, что это может предположить, что поддержка popcnt инструкция с -mpopcnt или -msse4.2 также включает векторные инструкции, которые были добавлены в том же поколении. См. опции . -march=nehalem GCC x86 (или -march= безотносительно ЦП, который Вы хотите, чтобы Ваш код принял, и настроиться для) мог быть хороший выбор. Выполнение получающегося двоичного файла на более старом ЦП приведет к отказу запрещенной команды.

Для создания двоичных файлов оптимизировал для машины, на которой Вы создаете их, используете -march=native (с gcc, лязгом или ICC).

MSVC обеспечивает внутреннее для инструкции x86 popcnt , но в отличие от gcc это - действительно внутреннее для аппаратной инструкции и требует поддержки оборудования.

<час>

Используя [1 111] вместо встроенного

В теории, любом компиляторе, который знает, как к popcount эффективно для целевого ЦП должен представить ту функциональность через C++ ISO std::bitset<> . На практике Вы могли бы быть более обеспечены с разрядным взломом AND/shift/ADD в некоторых случаях для некоторых целевых центральных процессоров.

Для целевых архитектур, где аппаратные средства popcount являются дополнительным расширением (как x86), не, все компиляторы имеют std::bitset, который использует в своих интересах его, когда доступно. Например, MSVC не имеет никакого способа включить popcnt поддержка во время компиляции, и всегда использует поиск по таблице , даже с [1 115] (который подразумевает SSE4.2, хотя технически существует отдельный бит функции для [1 116].)

, Но по крайней мере Вы получаете что-то портативное, которое работает везде, и с 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, лязга, 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 версия аргумента):

    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 является byte-at-a-time поиском по таблице. Это не замечательно для ARM, например .

Я особенно люблю этот пример из файла состояния:

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

мне нравится он лучше всего, потому что это настолько симпатично!

Что делает Вы имеете в виду с "Лучшим алгоритмом"? Закороченный код или постившийся код? Ваш очень изящный взгляд кода и это имеет постоянное время выполнения. Код также очень короток.

, Но если скорость является основным фактором а не размером кода тогда, я думаю, что следование может быть быстрее:

       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 битовых значения могут быть быстрее.

Это один из тех вопросов, на которых полезно знать вашу микроархитектуру. Я только что рассчитал время для двух вариантов в 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 гигациклами. Общее время работы процессора Core Duo с тактовой частотой 2,4 ГГц составляет 10,5 с. 25 гигациклов = чуть более 10 секунд на этой тактовой частоте, поэтому я уверен, что мои тайминги правильные.

Это связано с цепочками зависимостей инструкций, которые очень плохи для этого алгоритма. Я мог бы снова почти удвоить скорость, используя пару 64-битных регистров. На самом деле, если бы я был умным и немного раньше добавил бы x + y, я смог бы сократить некоторые сдвиги. 64-битная версия с некоторыми небольшими изменениями выйдет примерно ровной, но снова посчитает вдвое больше бит.

С 128-битными регистрами SIMD, еще одним множителем два, и наборы инструкций SSE также часто имеют хитроумные сокращения.

Нет причин для того, чтобы код был особенно прозрачным. Интерфейс прост, на алгоритм можно ссылаться в Интернете во многих местах, и он поддается всестороннему модульному тестированию. Программист, который наткнется на это, может даже чему-то научиться. Эти битовые операции чрезвычайно естественны на машинном уровне.

ОК, я решил протестировать улучшенную 64-битную версию. Для этого one 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;
}

Это выглядит примерно правильно (I ' m, хотя и не тестирую внимательно). Теперь тайминги выходят на 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, за 9,5 с прошло 384 миллиарда битов. Итак, есть еще 20% Теперь при 800 мс для 32 миллиардов бит.

убедитесь, что каждый аргумент достаточно отличается, чтобы 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, за 9,5 с прошло 384 миллиарда битов. Итак, есть еще 20% Теперь при 800 мс для 32 миллиардов бит.

убедитесь, что каждый аргумент достаточно отличается, чтобы 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, за 9,5 с прошло 384 миллиарда битов. Итак, есть еще 20% Теперь при 800 мс для 32 миллиардов бит.

потому что другой стенд не показывает тактовую частоту, но похоже, что я вытащил сопли из табличной версии на 64 КБ, что в первую очередь является трагическим использованием кеша L1.

Обновление: решил сделать очевидное и создать pop6 (), добавив еще четыре повторяющиеся строки. Получилось 22,8gc, за 9,5 секунды прошло 384 миллиарда битов. Итак, есть еще 20% Теперь при 800 мс для 32 миллиардов бит.

потому что другой стенд не показывает тактовую частоту, но похоже, что я вытащил сопли из табличной версии объемом 64 КБ, что в первую очередь является трагическим использованием кеша L1.

Обновление: решил сделать очевидное и создать pop6 (), добавив еще четыре повторяющиеся строки. Получилось 22,8gc, за 9,5 секунды прошло 384 миллиарда битов. Итак, есть еще 20% Теперь при 800 мс для 32 миллиардов бит.

Несколько открытых вопросов:-

1. Если число отрицательное, то?
2. Если число 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

Примерно в 1990 году я написал макрос быстрого подсчета битов для RISC-машин. Он не использует расширенную арифметику (умножение, деление,%), выборку из памяти (слишком медленно), переходы (слишком медленно), но предполагает, что ЦП имеет 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-строчной логической таблицы, подобной моей выше, если хотите.

• Дон Гиллис

Это - реализация в golang

func CountBitSet(n int) int {


    count := 0
    for n > 0 {
      count += n & 1
      n >>= 1

    }
    return count
}

C++ 20 std::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++

Простой способ, который должен хорошо работать для небольшого количества битов, это примерно так (для 4 бит в этом примере):

( i & 1) + (i & 2) / 2 + (i & 4) / 4 + (i & 8) / 8

Могут ли другие рекомендовать это для небольшого количества бит в качестве простого решения?