Подсчет битов в числе [дубликат]

Question

Дубликат:

Лучший алгоритм для подсчета количества установленных бит в 32-битном целом числе?

---

Предположим, у вас есть номер.Есть ли способ подсчитать биты, равные 1 в двоичном представлении этого числа, не используя итерацию?Я имею в виду, есть ли способ сделать это за постоянное время, используя некоторые побитовые операторы и маски.Мне нужно решение, которое будет хорошо работать как для 32-битной, так и для 64-битной архитектуры.Ах чуть не забыл, мне нужно для языка Си или ассемблера тоже хорошо.

Answer 1

Существует алгоритм подсчета битов без цикла http://graphics.stanford.edu/~seander/bithacks.html.Множество алгоритмов подсчета битов на http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Answer 2

Ну, конечно, есть, но вам это не понравится.

Конечно, вы можете создать таблицу поиска со всеми правильными значениями:

таблица[1] = 1, таблица[2] = 1, таблица[3] = 2 и т. д.

Итак, это даст вам действительно быстро ответ, но само по себе это совершенно бесполезное решение, поскольку таблица должна быть очень и очень большой.

Вы могли бы немного оптимизировать это, но это потребует лишь небольшой итерации.Просто создайте 8-битную версию табличного решения, простую таблицу из 256 записей, затем переберите каждый БАЙТ проверяемого значения, суммируя результаты поиска в таблице.Что-то вроде:

short int tableLookup[256] = { 0, 1, 1, 2, 1, ... };
unsigned int valueToCheck = 89392491;
int result = 0;
while ( valueToCheck != 0 ) {
   result += tableLookup[ (valueToCheck & 0xFF) ];
   valueToCheck >>= 8;
}
// result should now have the correct bit count, if the table is correct.

Хм, кажется, это хорошо известно (и здесь я это делал в уме):http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Answer 3

Да, вы можете сделать это, используя Справочная таблица.