Keil Logo

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


Did this article provide the answer you needed?
 
Yes
No
Not Sure
 
  Arm logo
Important information

This site uses cookies to store information on your computer. By continuing to use our site, you consent to our cookies.

Change Settings

Privacy Policy Update

Arm’s Privacy Policy has been updated. By continuing to use our site, you consent to Arm’s Privacy Policy. Please review our Privacy Policy to learn more about our collection, use and transfers
of your data.