Сколько 1 с в n-битном целом числе?

Question

Интересная проблема, с которой я столкнулся сегодня: какой самый быстрый способ подсчитать число 1 в n-битном целом числе? Можно ли победить O (n)?

Например:

42 = 0b101010 => 3 ones
512 = 0b1000000000 => 1 one

Ясно, что наивный алгоритм - просто считать. Но есть ли какие-нибудь хитрости, чтобы ускорить его?

(Это всего лишь академический вопрос; при реализации такой стратегии ожидаемого выигрыша в производительности нет.)

Answer 1

См. невероятную статью Bit Twiddling Hacks .

Answer 2

Вероятно, самым быстрым способом на процессорах x86 было бы использовать POPCNT класс инструкций.

Answer 3

Самый быстрый способ (без использования специальных функций процессора или сохранения предварительно рассчитанных ответов) - это И ваше значение со значением - 1 в цикле, пока не будет 0. Число итераций равно числу 1.

Answer 4

Если у вас есть конечное количество бит (например, 32 бита), вы можете предварительно рассчитать его, а затем просто посмотреть значение в массиве.

Несколько более практичный способ - сделать это для каждого байта или слова (занимает всего 256/64 Кбайт), а затем добавить результаты для каждого байта / слова в значение

Answer 5

O (log n) , если вы этого не сделаете за пределами машинных слов и игнорировать тот факт, что каждая машинная операция работает с n битами.

На практике вы должны использовать библиотечные функции вместо того, чтобы самостоятельно разбирать биты, например, Integer.bitCount () в Java.