language-agnosticbit-manipulationhammingweight

How many 1s in an n-bit integer?

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.)

Solution

  • See the fabulous Bit Twiddling Hacks article.