Monday, 9 June 2008

How many bits?

Sometimes you need to know how many bits there are in a binary representation of a number.

0 = 0
1 = 1
2 = 1
3 = 2
4 = 1
5 = 2
127 = 7
etc...

Anyway, there is a quicker way than just counting them in a loop.

first of all, break the problem down. To find the number of bits in a 32 bit int, find the sum of the bit counts in two 16 bit ints.
to find the number of bits in a 16 bit in, find the sum of the bit counts in two 8 bit ints.
to find the number of bits in a 8 bit in, find the sum of the bit counts in two 4 bit ints.
to find the number of bits in a 4 bit in, find the sum of the bit counts in two 2 bit ints.
to find the number of bits in a 2 bit in, find the sum of the bit counts in two 1 bit ints.
to find the number of bits in a 1 bit in, just use it's value.

oh, is that all... how exactley is that faster than just counting the bits? Well, you can count all the ones at the same time and sum them into 16 2 bit numbers.

0x55555555 == b01010101010101010101010101010101
0xAAAAAAAA == b10101010101010101010101010101010
count = ( value & 0x55555555 ) + ( ( value & 0xAAAAAAAA ) >> 1 )

This gives us the sums of all the pairs of 1 bit ints.

now we do the same with the pairs of 2 bits

count = ( count & 0x33333333 ) + ( ( count & 0xCCCCCCCC ) >> 2 )

then onward

count = ( count & 0x0F0F0F0F ) + ( ( count & 0xF0F0F0F0 ) >> 4 )
count = ( count & 0x00FF00FF ) + ( ( count & 0xFF00FF00 ) >> 8 )
count = ( count & 0x0000FFFF ) + ( ( count & 0xFFFF0000 ) >> 16 )

and value now contains the bit count of the whole 32 bit intial value.

counting the bits in a 64 bit value:

count = ( value & 0x5555555555555555 ) + ( ( value & 0xAAAAAAAAAAAAAAAA ) >> 1 )
count = ( count & 0x3333333333333333 ) + ( ( count & 0xCCCCCCCCCCCCCCCC ) >> 2 )
count = ( count & 0x0F0F0F0F0F0F0F0F ) + ( ( count & 0xF0F0F0F00xF0F0F0F0 ) >> 4 )
count = ( count & 0x00FF00FF00FF00FF ) + ( ( count & 0xFF00FF000xFF00FF00 ) >> 8 )
count = ( count & 0x0000FFFF0000FFFF ) + ( ( count & 0xFFFF0000FFFF0000 ) >> 16 )
count = ( count & 0x00000000FFFFFFFF ) + ( ( count & 0xFFFFFFFF00000000 ) >> 32 )

Ooh, wasn't that easy?