Bit Fiddling - 2

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.

In the next post we will look into some parallel counting, constant time without memory and then we will also look into some system defined functionalilty to do this.