Saturday, September 11, 2010
Counting bits in an integer
September 11th, 2010
I have simple approach as it was mentioned in the bit reversal algorithm. We can add the adjacent bits in each one bit position, two bit positions, four bit positions, etc… until we reach the number of bits in integer. I am providing pseudo code,
1. Add bits in positions (0, 1), (2, 3) so on (30, 31)
2. Add bits in positions (01, 23), (45, 67) so on (28 29, 30 31)
3. Add bits in positions (0123, 4567).....
4. Add bits in positions (01234567, 8 9 10 11 12 13 14 15)
5. Add the bits in first half and second half of the integer.
The algorithm takes log(N) steps to count the bits in integer.
An example will clarify it more clearly
Let us take 0x12345678, the corresponding binary representation can be written easily (it has 13 set bits)
After step 1 we get
After step 2 we get
After step 3 we get
After step 4 we get
After step 5 we get
– (13) Which is required result
The algorithm can be implemented using shifts and addition operation. There are multiple algorithms out there to compute number of set bits in an integer. For few of such algorithms see the following link
Depending on context we can choose right algorithm.