How many 1s are in an n-bit integer?

Question

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

For instance:

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

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

(This is just an academic question; when implementing such a strategy, the expected performance gain is not expected.)

Answer 1

See the fabulous article on battled hacks .

Answer 2

Probably the fastest way for x86 processors would be to use the POPCNT instruction class .

Answer 3

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

Answer 4

If you have a finite number of bits (e.g. 32 bits), you can pre-define it and then just look at the value in the array.

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

Answer 5

O (log n) , if you do not go beyond machine words and ignore the fact that each machine operation runs on n bits.

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