bit arithmetic

Write an algorithm to count the 1 bits in an integer?

I would use AND. The algorithm is simple. AND with 1, increment count accordingly and right shift till zero.

int get1BitsCount ( int x )
count = 0
while (x != 0):
  if ( x&1 == 1 ) count++ 
  x = x>>1
return count

The algorithm runs in O(n) where n are the number of bits in the integer.

Now, can we have a better one? Yes. No one would expect you to get this though. I did not get it either :D. But it is worth blogging.

Suppose you have a number like this 10001000. Normally, the way you can find if a bit is 1 is to use AND operation as X&1 gives X or use OR operation as X|0 gives X. Somehow, you have to get the first 1 (LSb) each time. That way you can increment the count and go to the next 1 LSb in a loop till 0.

You can subtract 1 to get 10000111 and then AND with 10001000 to get 10000000. Note than you have flipped the first 1 LSb. This is a very radical approach.

i.e.

int get1BitsCountRadical ( int x )
count = 0
while (x != 0):
  x = x&(x-1)
  count++
return count

This runs in O(m) where m is the number of bits. So 1000000 takes the same time as 00000001.