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)
00010010001101000101011001111000
00 01 00 10 00 11 01 00 01 01 01 10 01 11 10 00
After step 1 we get
00 01 00 01 00 10 01 00 01 01 01 01 01 10 01 00
After step 2 we get
00 01 00 01 00 10 01 00 01 01 01 01 01 10 01 00
0001 0001 0010 0001 0010 0010 0011 0001
After step 3 we get
0001 0001 0010 0001 0010 0010 0011 0001
00000010 00000011 00000100 00000100
After step 4 we get
00000010 00000011 00000100 00000100
0000000000000101 0000000000001000
After step 5 we get
0000000000000101 0000000000001000
00000000000000000000000000001101 – (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.
1 comment:
hey fella you have no idea of big o notation
Post a Comment