In the previous post we dicussed about some trivial straightforward ways of counting set bits. Here we will discuss some fast ways of doing this.

**4. Pre-Computing Bits:**

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.

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] ;

}

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.