GENERAL: COUNTING SET BITS IN A BYTE

QUESTION

Do you have any suggestions for the most efficient way to code a routine to count the number of set bits in a byte using the Keil compiler?

ANSWER

There are at least 3 ways to count the number of set bits in a byte:

1. The mask and shift approach.
2. The Brian Kernighan approach.
3. The index into an array approach.

The code for each of these is listed below.

Mask and Shift

unsigned char countbits_shift_method (unsigned char b)
{
unsigned char mask, count;

for (count = 0, mask = 0x80; mask != 0; mask >>= 1)
  {
  if (b & mask)
    count++;
  }

return (count);
}

Brian Kernighan

unsigned char countbits_bk_method (unsigned char b)
{
unsigned char count;

for (count = 0; b != 0; count++)
  {
  b &= b - 1; // this clears the LSB-most set bit
  }

return (count);
}

Index Into an Array

unsigned char parity_array [256] =
  { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ... };
  // Note that you need to fill-in this array

unsigned char countbits_array_method (unsigned char b)
{
return (parity_array [b]);
}

Last Reviewed: Monday, May 10, 2004