Построение логического выражения, которое будет считать биты в байте

Question

При собеседовании с новыми кандидатами мы обычно просим их написать фрагмент кода C для подсчета количества битов со значением 1 в данной байтовой переменной (например, байт 3 имеет два 1-битных).Я знаю все распространенные ответы, такие как смещение вправо восемь раз или индексирование таблицы констант из 256 предварительно вычисленных результатов.

Но есть ли более разумный способ без использования предварительно вычисленной таблицы?Какая кратчайшая комбинация байтовых операций (AND, OR, XOR, +, -, двоичное отрицание, сдвиг влево и вправо), которая вычисляет число 1-бит?

Answer 1

Существует как минимум два более быстрых решения с различными характеристиками производительности:

1. Вычтите одно и И новые и старые значения. Повторите до нуля. Подсчитайте количество итераций. Сложность: O (B), где B - число однобитных.

   int bits(unsigned n)
   {
       for (int i = 0; n; ++i)
       {
           n &= n - 1;
       }
       return i;
   }
   

2. Добавьте пары битов, затем группы по четыре, затем группы по восемь, пока не достигнете размера слова. Есть хитрость, которая позволяет добавлять все группы на каждом уровне за один проход. Сложность: O (log (N)), где N - общее количество бит.

   int bits(uint32 n)
   {
       n = (n & 0x55555555) + ((n >>  1) & 0x55555555);
       n = (n & 0x33333333) + ((n >>  2) & 0x33333333);
       n = (n & 0x0f0f0f0f) + ((n >>  4) & 0x0f0f0f0f);
       n = (n & 0x00ff00ff) + ((n >>  8) & 0x00ff00ff);
       n = (n & 0x0000ffff) + (n >> 16);
       return n;
   }
   

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

Answer 2

Вот список способов Бит тиддлинг хаков

Answer 3

Java делает это таким образом (используя 32-разрядные целые числа) (14 вычислений)

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

Для 16-разрядных целых чисел (коротких) метод можно переписать так:

private static int bitCount(int i) {
   // HD, Figure 5-2
   i = i - ((i >>> 1) & 0x5555);
   i = (i & 0x3333) + ((i >>> 2) & 0x3333);
   i = (i + (i >>> 4)) & 0x0f0f;
   i = i + (i >>> 4);
   i = i + (i >>> 8);
   return i & 0x3f;
}

Для 8-битных целых чисел (в байтах) это немного сложнее, но общая идея есть.

Вы можете проверить эту ссылку для получения дополнительной информации о функциях быстрого счета битов: http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Самый быстрый / простой способ для любого целого числа: O (0) для лучшего случая и O (n) для худшего (где n - количество битов в значении) -

static private int bitcount(int n)  {
   int count = 0 ;
   while (n != 0)  {
      count++ ;
      n &= (n - 1) ;
   }
   return count ;
}