Bit Counting

A collection of bit counting routines that I have collected over the years. Fun stuff to unroll and determine why they work.

//-------------------------------------
int bitcount(unsigned value)
{
   int count = 0;
   while (value) 
   {
      count += (value & 1)
      value >>= 1;
   }
   return count;
}


//-------------------------------------
int bitcount(int value)
{
   int count = 0;
   while (value) 
   {
      value &= (value - 1);
      count++;
   }
   return count;
}


//-------------------------------------
int bitcount(unsigned value)
{
   int count;

   for(count = value; value >>= 1; count -= value)  
   {  /* empty */  }

   return count;
}


//-------------------------------------
static char tab[] = {
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

int bitcount(int value)
{
   return tab[value>>24 & 0xff] 
        + tab[value>>16 & 0xff]
        + tab[value>>8  & 0xff] 
        + tab[value     & 0xff];
}


//-------------------------------------
int bitcount(int value)
{
   value = (value>>1 & 0x55555555) + (value & 0x55555555);
   value = (value>>2 & 0x33333333) + (value & 0x33333333);
   value = (value>>4 & 0x0f0f0f0f) + (value & 0x0f0f0f0f);
   value = (value>>8 & 0x00ff00ff) + (value & 0x00ff00ff);

   return (value >> 16) + (value & 0x0000ffff);
}


//-------------------------------------
int bitcount(int value)
{
   value = (value>>1 & 0x55555555) + (value & 0x55555555);
   value = (value>>2 & 0x33333333) + (value & 0x33333333);
   value = ((value>>4) + value) & 0x0f0f0f0f;
   value = ((value>>8) + value);

   return ((value>>16) + value) & 0x3f;
}


//-------------------------------------
int bitcount(int value)
{
   value = (value>>1 & 0x55555555) + (value & 0x55555555);
   value = (value>>2 & 0x33333333) + (value & 0x33333333);

   return (((value>>4) + value) & 0x0f0f0f0f) % 0xff;
}


//-------------------------------------
int bitcount(int value)
{
   value -= (value>>1 & 0x77777777) 
          + (value>>2 & 0x33333333) 
          + (value>>3 & 0x11111111);

   return (((value>>4) + value) & 0x0f0f0f0f) % 0xff;
}