Как реализовать Bitcount с использованием только побитовых операторов?

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

Разрешены только побитовые операции. Нет «если», «за» и т. Д.

int x = 4; printf("%d\n", x & 0x1); printf("%d\n", (x >> 1) & 0x1); printf("%d\n", (x >> 2) & 0x1); printf("%d\n", (x >> 3) & 0x1); 

Спасибо.

Из http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

 unsigned int v; // count bits set in this (32-bit value) unsigned int c; // store the total here c = v - ((v >> 1) & 0x55555555); c = ((c >> 2) & 0x33333333) + (c & 0x33333333); c = ((c >> 4) + c) & 0x0F0F0F0F; c = ((c >> 8) + c) & 0x00FF00FF; c = ((c >> 16) + c) & 0x0000FFFF; 

Изменить: По общему признанию, это немного оптимизировано, что затрудняет чтение. Его легче читать так:

 c = (v & 0x55555555) + ((v >> 1) & 0x55555555); c = (c & 0x33333333) + ((c >> 2) & 0x33333333); c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F); c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF); c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF); 

Каждый шаг этих пяти добавляет соседние биты в группы по 1, затем 2, затем 4 и т. Д. Метод основан на делении и покорении.

На первом этапе мы добавляем биты 0 и 1 и помещаем результат в два битовых сегмента 0-1, добавляем биты 2 и 3 и помещаем результат в двухбитовый сегмент 2-3 и т. Д. …

На втором этапе мы добавляем два бита 0-1 и 2-3 вместе и помещаем результат в 4-битный 0-3, складываем два бита 4-5 и 6-7 и помещаем результат в четырехбитовый 4-7 и т.д.

Пример:

 So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1) After the first step I have: 0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10 In the second step I have: 0000000100010011 ( 00+00 00+01 01+00 01+10 ) = 0000 0001 0001 0011 In the fourth step I have: 0000000100000100 ( 0000+0001 0001+0011 ) = 00000001 00000100 In the last step I have: 0000000000000101 ( 00000001+00000100 ) 

который равен 5, что является правильным результатом

Я бы использовал предварительно вычисленный массив

 uint8_t set_bits_in_byte_table[ 256 ]; 

i запись в этой таблице хранит количество заданных битов в байте i , например set_bits_in_byte_table[ 100 ] = 3 поскольку в двоичном представлении десятичного числа 100 (= 0x64 = 0110-0100) имеется 3 1 бит.

Тогда я попробую

 size_t count_set_bits( uint32_t x ) { size_t count = 0; uint8_t * byte_ptr = (uint8_t *) &x; count += set_bits_in_byte_table[ *byte_ptr++ ]; count += set_bits_in_byte_table[ *byte_ptr++ ]; count += set_bits_in_byte_table[ *byte_ptr++ ]; count += set_bits_in_byte_table[ *byte_ptr++ ]; return count; } 

Вот простую иллюстрацию к ответу :

 abcd 0 abc 0 b 0 d & & + 0 1 0 1 0 1 0 1 0 a 0 c ------- ------- ------- 0 b 0 d 0 a 0 c a+b c+d 

Таким образом, у нас есть ровно 2 бита для хранения + b и 2 бит для хранения c + d. a = 0, 1 и т. д., поэтому 2 бита – это то, что нам нужно для хранения их суммы. На следующем шаге у нас будет 4 бита для хранения суммы двухбитовых значений и т. Д.

Несколько интересных решений здесь .

Если вышеприведенные решения слишком скучны, здесь рекурсивная версия C исключает проверку состояния или цикл:

  int z(unsigned n, int count); int f(unsigned n, int count); int (*pf[2])(unsigned n, int count) = { z,f }; int f(unsigned n, int count) { return (*pf[n > 0])(n >> 1, count+(n & 1)); } int z(unsigned n, int count) { return count; } ... printf("%d\n", f(my_number, 0)); 
  • Что плохого в перестановке 32-битной переменной 32 бита?
  • Что такое бит-маска?
  • Битфилд-манипуляция в C
  • C / C ++ проверить, установлен ли один бит, т. Е. Переменная int
  • В C / C ++ какой самый простой способ изменить порядок бит в байте?
  • Как получить побитовые данные из целочисленного значения в C?
  • Что такое CHAR_BIT?
  • Java «Бит Shifting» Учебник?
  • Есть ли способ выполнить круговое смещение бита в C #?
  • BitSet с целым числом и длительностью
  • Арифметический бит-сдвиг по целому знаку со знаком
  • Давайте будем гением компьютера.