Q: Find the number of set bits in a given integer?
Sol: Pre-Computing Bits
static unsigned int NumBits8Bit[256] ;
//Precompute this array of size 256, each element in the array denoting the number of bits in a char (0x00 to 0xff). Then separate divide the number of interest into 4 blocks of 8 bits each by masking the last 8 bits (ANDing it with 0xffU) and right shifting by 8 bits each time. Sum up the count and return
int BitCount (unsigned int u)
{
return NumBits8Bit [u & 0xffU]
+ NumBits8Bit [(u>> 8 ) & 0xffU]
+ NumBits8Bit [(u>>16) & 0xffU]
+ NumBits8Bit [(u>>24) & 0xffU] ;
}
The fastest ways to solve this problem is through look-up tables. But, like everything else, it comes with a cost. Here, you pay for memory.
You can write several variations to this algorithm, basically changing the amount of bits you want to pre-compute. But, remember that the more bits you pre-compute, the lesser the number of look-ups. In most common cases you can precompute 4,8,16 bits. Doing a 32-bit lookup will take up quite some memory.