How many 1s in an n-bit integer?

Question

An interesting problem I ran into today: what is the fastest way to count the number of 1s in an n-bit integer? Is it possible to beat O(n)?

For example:

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

Clearly, the naive algorithm is to simply count. But, are there any tricks to speed it up?

(This is merely an academic question; there is no expected performance gain by implementing such a strategy.)

Answer 1

See the fabulous Bit Twiddling Hacks article.

Answer 2

If you have a finite number of bits (eg 32 bits) you can precalcualte it and then just look up the value in an array.

A slightly more practical way is to do this for each byte or word (only takes 256/64k bytes) and then add the results for each byte/word in the value

Answer 3

Probably the fastest way on x86 processors would be to use the POPCNT class of instructions.

Answer 4

The fastest way (without using special processor features or storing pre-calculated answers) is to AND your value with value - 1 in a loop until it's 0. The number of iterations is the number of 1's.

Answer 5

O(log n), if you don't go beyond machine words and disregard the fact that each machine operation operates on n bits.

In practice you should use library functions instead of twiddling the bits yourself, for example Integer.bitCount() in Java.