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

868

8 битов, представляющих число 7, выглядят так:

00000111

Три бита установлены.

Какие существуют алгоритмы для определения количества установленных бит в 32-битном целом числе?

Мэтт Хауэллс
источник
101
Это вес Хэмминга.
Purfideas
11
Что такое реальное приложение для этого? (Это не должно восприниматься как критика - мне просто любопытно.)
jonmorgan
8
Вычисление бита четности (посмотрите), который использовался как простое обнаружение ошибок в коммуникации.
Диалектик
8
@Dialecticus, вычисление бита четности дешевле, чем вычисление веса Хэмминга
finnw
15
@spookyjon Допустим, у вас есть граф, представленный в виде матрицы смежности, которая по сути является битовой. Если вы хотите вычислить количество ребер вершины, это сводится к вычислению веса Хэмминга одной строки в наборе битов.
fuz

Ответы:

850

Это известно как « Вес Хэмминга », «Попконт» или «Боковое дополнение».

«Лучший» алгоритм действительно зависит от того, на каком процессоре вы находитесь и какова ваша схема использования.

Некоторые процессоры имеют одну встроенную инструкцию для этого, а другие имеют параллельные инструкции, которые действуют на битовые векторы. Параллельные инструкции (например, x86 popcntна процессорах, где они поддерживаются) будут почти наверняка самыми быстрыми. Некоторые другие архитектуры могут иметь медленную инструкцию, реализованную с помощью микрокодированного цикла, который проверяет бит за цикл ( требуется цитирование ).

Предварительно заполненный метод поиска в таблице может быть очень быстрым, если ваш ЦП имеет большой кэш и / или вы выполняете много этих инструкций в узком цикле. Однако он может пострадать из-за «пропуска кэша», когда ЦП должен извлечь часть таблицы из основной памяти. (Посмотрите каждый байт отдельно, чтобы таблица была маленькой.)

Если вы знаете, что ваши байты будут в основном 0 или 1, то есть очень эффективные алгоритмы для этих сценариев.

Я считаю, что очень хорошим алгоритмом общего назначения является следующий, известный как «параллельный» или «алгоритм SWAR переменной точности». Я выразил это на C-подобном псевдо-языке, вам может потребоваться настроить его для работы с конкретным языком (например, используя uint32_t для C ++ и >>> в Java):

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and 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;
}

Для JavaScript: принуждать к целому числу с |0для выполнения: изменение первой линииi = (i|0) - ((i >> 1) & 0x55555555);

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


Как работает этот SWAR Bithack:

i = i - ((i >> 1) & 0x55555555);

Первый шаг - это оптимизированная версия маскирования, чтобы изолировать нечетные / четные биты, сдвинуть их в линию и добавить. Это эффективно делает 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 может превзойти параллельную реализацию SSSE3PSHUFB примерно в 2 раза, но только если ваш компилятор все делает правильно . В противном случае SSE может выйти значительно вперед. Более новые версии компилятора знают о проблеме ложной зависимости popcnt от Intel .

Ссылки:

Matt Howells
источник
87
ха! Мне нравится функция NumberOfSetBits (), но удачи вам в проверке кода. :-)
Джейсон С
37
Может быть, это следует использовать unsigned int, чтобы легко показать, что он свободен от каких-либо знаковых битовых осложнений. Также было uint32_tбы безопаснее, как, например, вы получаете то, что ожидаете на всех платформах?
Крейг МакКуин
35
@nonnb: На самом деле, как написано, код содержит ошибки и нуждается в обслуживании. >>определяется реализацией для отрицательных значений. Аргумент должен быть изменен (или приведен) на unsigned, и, поскольку код является 32-битным, его, вероятно, следует использовать uint32_t.
R .. GitHub ОСТАНОВИТЬ ЛЬДА
6
Это не совсем волшебство. Это добавляет наборы битов, но делает это с некоторыми умными оптимизациями. Ссылка на википедию, приведенная в ответе, хорошо объясняет, что происходит, но я буду идти построчно. 1) Подсчитайте количество битов в каждой паре битов, поместив это количество в эту пару битов (у вас будет 00, 01 или 10); «умный» бит здесь - это вычитание, которое избегает одной маски. 2) Добавьте пары этих сумм бит-пар в их соответствующие кусочки; ничего хитроумного, но каждый клев теперь будет иметь значение 0-4. (продолжение)
dash-tom-bang
8
Еще одно замечание: это распространяется на 64- и 128-битные регистры, просто расширяя константы соответствующим образом. Интересно (мне), что эти константы также ~ 0/3, 5, 17 и 255; первые три были 2 ^ n + 1. Все это имеет больше смысла, чем больше вы смотрите на это и думаете об этом в душе. :)
dash-tom-bang
214

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

Например, на компиляторе 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 предоставляет встроенную функцию для 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 для архитектур, которые его поддерживают.

#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, например .

Peter Cordes
источник
5
Я согласен, что это хорошая практика в целом, но на XCode / OSX / Intel я обнаружил, что он генерирует более медленный код, чем большинство предложений, размещенных здесь. Смотрите мой ответ для деталей.
5
Intel i5 / i7 имеет инструкцию SSE4 POPCNT, которая делает это, используя регистры общего назначения. GCC в моей системе не выдает эту инструкцию, используя эту встроенную функцию, я думаю, из-за опции -march = nehalem пока нет.
Матя
3
@matja, мой GCC 4.4.1 выдает команду popcnt, если я компилирую с -msse4.2
Нильс Пипенбринк,
74
использовать с ++ std::bitset::count. после встраивания это компилируется в один __builtin_popcountвызов.
deft_code
1
@nlucaroni Ну, да. Времена меняются. Я написал этот ответ в 2008 году. В настоящее время у нас есть собственный popcount, и встроенная функция будет скомпилирована в один оператор на ассемблере, если платформа позволяет это.
Нильс Пипенбринк,
184

На мой взгляд, «лучшее» решение - это то, которое может быть прочитано другим программистом (или первым программистом два года спустя) без обильных комментариев. Возможно, вы захотите самое быстрое или умное решение, которое некоторые уже предоставили, но я предпочитаю удобство чтения в любое время.

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

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

paxdiablo
источник
21
Вместо того, чтобы делить на 2 и комментировать его как «биты сдвига ...», вы должны просто использовать оператор сдвига (>>) и оставить комментарий.
индивидуум
9
не будет ли больше смысла заменить if ((value & 1) == 1) { count++; }на count += value & 1?
Ponkadoodle
21
Нет, лучшее решение не самое читаемое в этом случае. Здесь самый лучший алгоритм самый быстрый.
NikiC
21
Это полностью твое мнение, @nikic, хотя ты можешь меня опровергнуть, очевидно. В вопросе не было упоминания о том, как количественно определить «лучший», слова «производительность» или «быстрый» нигде не видно. Вот почему я выбрал для чтения.
paxdiablo
3
Я читаю этот ответ 3 года спустя и считаю его лучшим ответом, потому что он читабелен и содержит больше комментариев. период.
вака-вака-вака
98

От восторга хакера, с. 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-ти инструкции (зависит от арки), без ветвления.

Восторг Хакер это восхитительно! Настоятельно рекомендуется.

Кевин Литтл
источник
8
Метод Java Integer.bitCount(int)использует ту же самую точную реализацию.
Марко Болис
После этого возникли небольшие проблемы - как бы это изменилось, если бы мы заботились только о 16-битных значениях вместо 32-битных?
Джереми Блум
Может быть, восторг хакеров восхитителен, но я бы дал хороший удар любому, кто называет это popвместо population_count(или pop_cntесли у вас должно быть сокращение). @MarcoBolis Я предполагаю, что это будет справедливо для всех версий Java, но официально это будет зависеть от реализации :)
Maarten Bodewes
И это не требует умножения, как код в принятом ответе.
Алекс
Обратите внимание, что при обобщении на 64-разрядные проблемы есть. Результат не может быть 64 из-за маски.
Альберт ван дер Хорст
76

Я думаю, что самый быстрый способ - без использования таблиц поиска и 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слов.

видит
источник
О чем это c = ? Похоже, это должно быть устранено. Кроме того, предложите дополнительный набор A "(((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24", чтобы избежать некоторых классических предупреждений.
chux - Восстановить Монику
4
Важной особенностью является то, что эта 32-битная процедура работает как для, так popcount(int v)и для popcount(unsigned v). Для переносимости, рассмотрите popcount(uint32_t v), и т.д. Действительно как часть * 0x1010101.
Chux - Восстановить Монику
соус? (книга, ссылка, имена и т.д.) будет ОЧЕНЬ приветствоваться. Потому что тогда мы можем вставить это в наши кодовые базы с комментарием, откуда это берется.
v.oddou
1
Я думаю, для большей ясности последняя строка должна быть записана так: return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;нам не нужно считать буквы, чтобы увидеть, что вы на самом деле делаете (так как вы отбросили первую 0, я случайно подумал, что вы использовали неправильный (перевернутый) битовый шаблон в качестве маски - то есть, пока я не заметил, что есть только 7 букв, а не 8).
emem
Это умножение на 0x01010101 может быть медленным, в зависимости от процессора. Например, в моем старом PowerBook G4 1 умножение было примерно таким же медленным, как 4 сложения (не так плохо, как деление, где 1 деление было примерно таким же медленным, как 23 сложения).
Джордж Келер
54

Мне стало скучно, и я рассчитал миллиард итераций трех подходов. Компилятор 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 КБ ОЗУ, используйте второй подход. В противном случае используйте читаемый (но медленный) подход, основанный на одном бите.

Трудно придумать ситуацию, в которой вы захотите использовать сложный подход.

Изменить: Подобные результаты здесь .

Майк Ф
источник
49
@Mike, табличный подход непобедим, если таблица находится в кеше. Это происходит в микро-бенчмарках (например, миллионы тестов в тесной петле). Тем не менее, промах кеша занимает около 200 циклов, и даже самый наивный попкорн здесь будет быстрее. Это всегда зависит от приложения.
Нильс Пипенбринк
10
Если вы не вызываете эту подпрограмму несколько миллионов раз в замкнутом цикле, у вас нет причин вообще заботиться о ее производительности, и вы также можете использовать наивный, но читаемый подход, поскольку потеря производительности будет незначительной. И FWIW, 8-битная LUT нагревается до 10-20 вызовов.
6
Я не думаю, что это так сложно представить себе ситуацию, когда это листовой вызов, сделанный из метода - фактически выполняющего тяжелую работу - в вашем приложении. В зависимости от того, что еще происходит (и продвигается), меньшая версия может выиграть. Было написано множество алгоритмов, которые побеждают своих сверстников благодаря лучшей локализации ссылок. Почему не это тоже?
Джейсон
Попробуйте это с помощью clang, это значительно умнее при реализации встроенных функций.
Мэтт Джоунер
3
GCC не будет выдавать команду popcont, если она не вызвана с -msse4.2, случай быстрее, чем «боковое сложение».
lvella
54

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

Нетер
источник
Когда Sun предоставила разные API, она должна использовать некоторую логику в фоновом режиме, верно?
Валлабх Патад
2
Как примечание, реализация Java использует тот же алгоритм, на который указал Кевин Литтл .
Марко Болис
2
Помимо реализации, это, пожалуй, самое ясное сообщение о намерениях для разработчиков, поддерживающих ваш код после вас (или когда вы вернетесь к нему через 6 месяцев)
divillysausages
31
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)
+-------------------------------+
abcdabcd987
источник
7
Этот алгоритм является версией, опубликованной Мэттом Хауэллсом, до того, как его оптимизировали до того, что он стал нечитаемым.
Лефтерис E
29

Это один из тех вопросов, который помогает узнать вашу микроархитектуру. Я просто рассчитал два варианта в 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 + ya немного раньше, я мог бы сбрить некоторые смены. 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 млрд бит.

user183351
источник
2
Лучшая не ассемблерная форма, подобная этой, я видел развернутые 24 32-битных слова за раз. dalkescientific.com/writings/diary/popcnt.c , stackoverflow.com/questions/3693981/… , dalkescientific.com/writings/diary/archive/2008/07/05/…
Мэтт
29

Почему бы итеративно не разделить на 2?

count = 0
пока n> 0
  if (n% 2) == 1
    считать + = 1
  п / = 2  

Я согласен, что это не самый быстрый, но «лучший» несколько двусмысленно. Я бы сказал, что «лучшее» должно иметь элемент ясности

Дэниел
источник
Это сработает и это легко понять, но есть более быстрые методы.
Мэтт Хауэллс
2
Если вы не сделаете это МНОГО , влияние на производительность будет незначительным. Так что при прочих равных я согласен с Даниэлем в том, что «лучшее» подразумевает «не читается как бред».
2
Я сознательно не определил «лучший», чтобы получить множество методов. Давайте посмотрим правде в глаза, если мы опустились до уровня такого рода хитрости, мы, вероятно, ищем что-то сверхбыстрое, похожее на шимпанзе, набравшего это.
Мэтт Хауэллс
6
Плохой код Компилятор может извлечь из этого пользу, но в моих тестах GCC этого не сделал. Заменить (n% 2) на (n & 1); И быть намного быстрее, чем MODULO. Заменить (n / = 2) на (n >> = 1); сдвиг бит намного быстрее, чем деление.
Меки
6
@Mecki: в моих тестах gcc (4.0, -O3) делал очевидные оптимизации.
26

Бит-тредлинг от восторга Хакера становится намного понятнее, когда вы записываете битовые паттерны.

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

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

John Dimm
источник
3
Это решение, кажется, имеет незначительную проблему, связанную с приоритетом оператора. Для каждого термина следует указать: x = (((x >> 1) & 0b01010101010101010101010101010101) + (x & 0b01010101010101010101010101010101)); (т.е. добавлены дополнительные символы).
Нопик
21

Для счастливого среднего между таблицей поиска 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

PhirePhly
источник
Не портативный Что если процессор имеет 9-битные байты? Да, существуют настоящие процессоры, подобные этому ...
Роберт С. Барнс,
15
@ Роберт С. Барнс, эта функция все еще будет работать. Он не делает никаких предположений о собственном размере слова и вообще не ссылается на «байты».
finnw
19

Это можно сделать там O(k), где kустановлено количество битов.

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}
оборота herohuyongtao
источник
По сути, это алгоритм Брайана Кернигана (помните его?), С небольшим изменением в том, что он использовал более лаконичную n &= (n-1)форму.
Адриан Моул
17

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

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);
    }
}
Peter
источник
4
о, мне это нравится как насчет версии Python: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))()
опустошение
10

Функцию, которую вы ищете, часто называют «суммой сбоку» или «счетчиком чисел» двоичного числа. Кнут обсуждает это в предисловии 1А, сс.11-12 (хотя в томе 2, 4.6.3- (7) была краткая ссылка).

« Locus classicus» - это статья Питера Вегнера «Методика подсчета в двоичном компьютере», из сообщения ACM , том 3 (1960), номер 5, стр. 322 . Там он приводит два разных алгоритма, один из которых оптимизирован для чисел, которые, как ожидается, будут «разреженными» (т. Е. Иметь небольшое количество единиц), а другой - для противоположного случая.

Michael Dorfman
источник
10
  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;
    }
стэктай
источник
9

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

  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

Бабан
источник
9

Я думаю, что метод Брайана Кернигана тоже будет полезен ... Он проходит столько итераций, сколько есть установленных битов. Так что, если у нас есть 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 г. в книге, отредактированной Беккенбахом)».

Erorr
источник
8

Я использую приведенный ниже код, который является более интуитивным.

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

Логика: n & (n-1) сбрасывает последний установленный бит n.

PS: я знаю, что это не O (1) решение, хотя и интересное решение.

оборота Маниш Мулани
источник
это хорошо для "разреженных" чисел с небольшим количеством битов, как это O(ONE-BITS). Это действительно O (1), поскольку существует не более 32 однобитных.
Ealfonso
7

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

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

       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-битное может быть быстрее.

Horcrux7
источник
Мой код имеет 10 операций. Ваш код имеет 12 операций. Ваша ссылка работает с меньшими массивами (5). Я использую 256 элементов. С кешированием могут быть проблемы. Но если вы используете его очень часто, то это не проблема.
Horcrux7
Этот подход измеримо немного быстрее, чем подход с переворотом, как выясняется. Что касается использования большего количества памяти, он компилируется с меньшим количеством кода, и это усиление повторяется каждый раз, когда вы включаете функцию. Так что это может легко оказаться чистой победой.
7

Я написал быстрый макрос для подсчета числа битов для машин 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 строками, как у меня выше.

  • Дон джиллис
оборота systemBuilder
источник
7

если вы используете 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 ++, и он просто развертывает ваш цикл для вас, если для подсчета битов используется постоянное значение (другими словами, я уверен, что это самый быстрый общий метод ты найдешь)

пентафоб
источник
К сожалению, подсчет битов не выполняется параллельно, поэтому он, вероятно, медленнее. Может быть, хорошо, constexprхотя.
Ималлетт
Согласен - это было забавное упражнение в рекурсии шаблонов C ++, но определенно довольно наивное решение.
Пентафоб
6

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

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

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

Росс
источник
1
Как это работает по сравнению с другими предложениями?
asdf
6

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);
         }
Rahul
источник
Не совсем алгоритм, это просто вызов библиотеки. Полезно для Java, не так много для всех остальных.
Бензадо
2
@benzado прав, но в любом случае +1, потому что некоторые разработчики Java могут не знать о методе
finnw
@finnw, я один из тех разработчиков. :)
neevek
6

Я нашел реализацию подсчета битов в массиве с использованием инструкции 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];
}
оборота ErmIg
источник
6

Я всегда использую это в конкурентном программировании, и это легко написать и эффективно:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}
diugalde
источник
5

Есть много алгоритмов для подсчета установленных битов; но я думаю, что лучший - быстрее! Вы можете увидеть подробности на этой странице:

Бит Тиддлинг Хаки

Я предлагаю это:

Подсчет битов, установленных в 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.

Мостафа
источник
5

Быстрое решение 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
    };
}
дадхи
источник
По иронии судьбы, эта таблица могла быть создана с помощью любого из алгоритмов, опубликованных в этой теме! Тем не менее, использование таких таблиц означает постоянную производительность. Следовательно, если пойти еще дальше и создать таблицу перевода 64 КБ, это приведет к уменьшению вдвое необходимых операций AND, SHIFT и ADD. Интересная тема для бит манипуляторов!
user924272
Большие таблицы могут быть медленнее (и не постоянно) из-за проблем с кешем. Вы можете «искать» 3 бита одновременно (0xe994 >>(k*2))&3, без доступа к памяти ...
greggo
5

Вот портативный модуль (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
Robert S. Barnes
источник
1
Мне очень нравится ваш плагин, полиморфный подход, а также переключатель для сборки в виде библиотеки многократного использования или автономного тестового исполняемого файла. Очень хорошо продумано =)
5

что вы можете сделать, это

while(n){
    n=n&(n-1);
    count++;
}

логика, лежащая в основе этого, состоит в том, что биты n-1 инвертированы из крайнего правого установленного бита n. если n = 6, т.е. 110, то 5 равно 101, биты инвертируются из крайнего правого установленного бита n. так что если мы и эти два мы сделаем самый правый бит 0 в каждой итерации и всегда перейдем к следующему крайнему правому установленному биту. Считаем установленный бит. Наихудшая временная сложность будет O (logn), когда каждый бит установлен.

Varun Gusain
источник