Count number of 1's in binary representation

TimeToCodeTheRoad picture TimeToCodeTheRoad · Jan 15, 2012 · Viewed 151.1k times · Source

Efficient way to count number of 1s in the binary representation of a number in O(1) if you have enough memory to play with. This is an interview question I found on an online forum, but it had no answer. Can somebody suggest something, I cant think of a way to do it in O(1) time?

Answer

Óscar López picture Óscar López · Jan 15, 2012

That's the Hamming weight problem, a.k.a. population count. The link mentions efficient implementations. Quoting:

With unlimited memory, we could simply create a large lookup table of the Hamming weight of every 64 bit integer