How many 1s in an n-bit integer?

An interesting problem I ran into today: wha开发者_运维百科t 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.)

See the fabulous Bit Twiddling Hacks article.

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

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.

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

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.