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.

## No comments:

## Post a Comment