Как реализовать Bitcount, используя только побитовые операторы?

Question

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

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

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

Спасибо.

Answer 1

С 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 и т. Д. 1010 *

На втором шаге мы складываем два бита 0-1 и 2-3 и помещаем результат в четырехбитовый 0-3, складываем два бита 4-5 и 6-7 и помещаем результат в 4-битные 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, что является правильным результатом

Answer 2

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

uint8_t set_bits_in_byte_table[ 256 ];

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

Тогда я бы попробовал

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

Answer 3

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

a b c d       0 a b c       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 бита для хранения a + b и 2 бита для хранения c + d. a = 0, 1 и т. д., поэтому 2 бита - это то, что нам нужно для хранения их суммы. На следующем шаге у нас будет 4 бита для хранения суммы 2-битных значений и т. Д.

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