ARM Technical Support Knowledge Articles

COUNTING SET BITS IN A BYTE

Applies to: General Topics

Answer

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

Article last edited on: 2004-05-10 21:25:39

Rate this article

[Bad]
|
|
[Good]
Disagree? Move your mouse over the bar and click

Did you find this article helpful? Yes No

How can we improve this article?

Link to this article
Copyright © 2011 ARM Limited. All rights reserved. External (Open), Non-Confidential