Как получить количество 1s от 64 битного числа

Question

Возможный дубликат: Count number of bits in a 64-bit (long, big) integer?

Для алгоритма сравнения изображения я получаю номер 64-битной, как результат. Количество 1s в числе (ulong) (101011011100 ...) говорит мне, как похожи два изображения, поэтому мне нужно их подсчитать. Как мне лучше сделать это на C#? Я бы хотел использовать это в приложении Windows Phone &, поэтому я также ищу недорогой метод.

EDIT: Мне нужно подсчитать бит для большого количества изображений, мне интересно, может ли быть лучше подход lookup-table. Но я не совсем уверен, как это работает ...

Answer 1

Sean Eron Anderson's Bit Twiddling Hacks имеет этот прием, среди прочего:

Подсчет битов, установленных параллельно

unsigned int v; // count bits set in this (32-bit value) 
unsigned int c; // store the total here 
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers 
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF}; 

c = v - ((v >> 1) & B[0]); 
c = ((c >> S[1]) & B[1]) + (c & B[1]); 
c = ((c >> S[2]) + c) & B[2]; 
c = ((c >> S[3]) + c) & B[3]; 
c = ((c >> S[4]) + c) & B[4]; 

The B массива, выраженное в двоичной форме, является:

B[0] = 0x55555555 = 01010101 01010101 01010101 01010101 
B[1] = 0x33333333 = 00110011 00110011 00110011 00110011 
B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111 
B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111 
B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111 

Мы можем настроить метод для больших целых размеров на продолжая шаблоны для двоичных магических чисел, B и S. Если есть k бит, нам нужны массивы S и B, чтобы быть потолочными (lg (k)) элементами длинными, и мы должны вычислить одинаковое количество выражений для c, поскольку S или B являются длинными. Для 32-битного v используются 16 операций. Лучший метод для подсчета битов в 32-разрядное целое число V является следующее:

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

Лучший метод бита подсчета занимает всего 12 операций, которая является такой же, как метод поиска стола, но избегает память и потенциальные недостатки кэша таблицы. Это гибрид между чисто параллельным методом выше и более ранними методами с использованием умножений (в разделе о подсчете битов с 64-битными инструкциями), хотя он не использует 64-битные инструкции. Количество бит, заданное в байтах, выполняется параллельно, а сумма битов, установленных в байтах, вычисляется путем умножения на 0x1010101 и смещения правых 24 бит.

Обобщенные лучший бит методом подсчета на целых битовых ширины Шифрование до 128 (параметризовано типа Т) заключается в следующем:

v = v - ((v >> 1) & (T)~(T)0/3);       // temp 
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);  // temp 
v = (v + (v >> 4)) & (T)~(T)0/255*15;      // temp 
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count 

Answer 2

Что-то вроде этих строк сделало бы (обратите внимание, что это не проверенный код, я просто написал его здесь, чтобы он мог и, возможно, потребовал настройки).

int numberOfOnes = 0; 
for (int i = 63; i >= 0; i--) 
{ 
    if ((yourUInt64 >> i) & 1 == 1) numberOfOnes++; 
    else continue; 
} 

Answer 3

это 32-битная версия BitCount, вы могли бы легко расширьте это до 64-битной версии, добавив еще один сдвиг вправо на 32, и это будет очень эффективно.

int bitCount(int x) { 
/* first let res = x&0xAAAAAAAA >> 1 + x&55555555 
* after that the (2k)th and (2k+1)th bits of the res 
* will be the number of 1s that contained by the (2k)th 
* and (2k+1)th bits of x 
* we can use a similar way to caculate the number of 1s 
* that contained by the (4k)th and (4k+1)th and (4k+2)th 
* and (4k+3)th bits of x, so as 8, 16, 32 
*/ 
    int varA = (85 << 8) | 85; 
    varA = (varA << 16) | varA; 
    int res = ((x>>1) & varA) + (x & varA); 

    varA = (51 << 8) | 51; 
    varA = (varA << 16) | varA; 
    res = ((res>>2) & varA) + (res & varA); 

    varA = (15 << 8) | 15; 
    varA = (varA << 16) | varA; 
    res = ((res>>4) & varA) + (res & varA); 

    varA = (255 << 16) | 255; 
    res = ((res>>8) & varA) + (res & varA); 

    varA = (255 << 8) | 255; 
    res = ((res>>16) & varA) + (res & varA); 
    return res; 
} 

Answer 4

Вариант 1 - меньше итераций, если результат 64-битных < 2^63:

byte numOfOnes; 
while (result != 0) 
{ 
    numOfOnes += (result & 0x1); 
    result = (result >> 1); 
} 

return numOfOnes; 

Вариант 2 - постоянное число interations - можно использовать разворачивания цикла:

byte NumOfOnes; 

for (int i = 0; i < 64; i++) 
{ 
    numOfOnes += (result & 0x1); 
    result = (result >> 1); 
}