Эффективнейшие методы для нахождения единиц в двоичном виде числа

#алгоритм #математика

Дано число в двоичной системе исчисления, например 10011010.
Какие есть эффективные методы узнать количество битов в этом числе, в которых значение
равно TRUE?  

Я придумал только два:  


Число & 1 и если равно 1, то увеличивать счетчик, а потом число сдвигать на один
в право.  
Создать lookup table в котором индех - это числа от 0 до 255, а значение это кол-во
едениц в этом числе.


Какие еще есть методы?
    

Ответы

Ответ 1

Самый эффективный метод следующий: пока число (его надо интерпретировать как беззнаковое
число, чтобы подсчитать все единицы), допустим n, не равно нулю выполнить следующую
операцию

n &= n - 1;


и соответственно увеличить счетчик единиц на единицу.

Принцип следующий. Допустим в числе имеется одна 1

0b00100000


Если из этого числа вычесть 1, то получится

0b00011111


Теперь если применить бинарную операцию И, то получим

0b00100000
&
0b00011111
==========
0b00000000


Число стало равным 0, следовательно оно содержало только одну 1, так как данная операция
была проделана только один раз.

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


Ответ 2

Ознакомился со статьёй по ссылке от VladD.
Оптимальный метод для 32-разрядного слова содержит 3 строчки суммарно на 12 операций:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count


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

P.S. (17.11.2017)
Если речь идёт о младших 32 разрядах слова большей разрядности, то ранее приведённый
алгоритм требует дополнительной очистки верхних разрядов с &= 0x3F.

Стал актуальным алгоритм для 64-битного слова (3 строчки, 12 операций):

v = v - ((v >> 1) & 0x5555555555555555);                        // sums in pairs
of bits, g+l=(2g+l)-l  
v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333); // sums in tetrades
c = (((v + (v >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x101010101010101) >> 56; // total sum


Алгоритм собирает сумму по методу двоичного слияния.
При сложении чётных и нечётных битов использовано тождество: g+l = (2g+l)-l.
При слиянии побайтовых сумм значимы только 7 младших разрядов, и верхние разряды
обрезаются один раз.  

Кстати: при использовании масок можно подсчитать сумму любых битов 64-разрядного слова.


Ответ 3

Раз уж пошла речь об ассемблере, в Intel'овских процессорах, поддерживающий SSE4,
есть инструкция POPCNT (в 16-, 32- и 64-разрядном вариантах), которая прямо считает
количество единичных бит. Этот вариант упомянут в статье, на которую сослался @jfs
в комментариях к вопросу.



Эта инструкция не доступна прямо в языке, но доступна в популярных компиляторах как
интринсик (функция-расширение, специфическая для компилятора):


__builtin_popcount, __builtin_popcountl, __builtin_popcountll в gcc (спасибо @avp
за наводку),
__popcnt16, __popcnt, __popcnt64 в MSVC,
clang поддерживает те же имена, что и у gcc.


Ответ 4

Кроме классического Кернигановского способа, приведённого @Vlad from Moscow, есть
ещё несколько. Почитайте здесь. (И гуглится по запросу «bit hacks».)

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