Конструкция логическое выражение, которое будет считать биты в байте
При интервьюировании новых кандидатов мы обычно просим, чтобы они записали часть кода C для подсчета числа битов со значением 1 в данной переменной байта (например, байт 3 имеет два 1 бит). Я знаю все общие ответы, такие как право, смещающееся восемь раз или индексирующее постоянную таблицу 256 предварительно вычисленных результатов.
Но, есть ли более умный путь, не используя предварительно вычисленную таблицу? Какова самая короткая комбинация операций байта (И, ИЛИ, XOR, +, - двоичное отрицание, левый и правый сдвиг), который вычисляет число 1 бита?
3 ответа
как минимум два более быстрых решения с разными характеристиками производительности:
Вычтите единицу и И новое и старое значения. Повторяйте до нуля. Подсчитайте количество итераций. Сложность: O (B), где B - количество однобитовых.
биты int (n без знака) { для (int i = 0; n; ++ i) { n & = n - 1; } вернуть я; }Добавляйте пары битов, затем группы по четыре, затем группы по восемь, пока не достигнете размера слова. Есть трюк, который позволяет вам добавлять все группы на каждом уровне за один проход. Сложность: O (log (N)), где N - общее количество бит.
int бит (uint32 n) { п = (п & 0x55555555) + ((п >> 1) & 0x55555555); п = (п & 0x33333333) + ((п >> 2) & 0x33333333); п = (п & 0x0f0f0f0f) + ((п >> 4) & 0x0f0f0f0f); n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff); п = (п & 0x0000ffff) + (п >> 16); return n; }Эта версия немного наивна. Если немного подумать, можно избежать некоторых операций.
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 ;
}