1

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?
Counting the number of bits that are set

How to find the number of bits set in an unsigned integer when it is allowed to iterate the loop same number of times as the number of bits set (if 3 bits are set, you can iterate the loop only 3 times)

Community
  • 1
  • 1
webgenius
  • 856
  • 3
  • 13
  • 30
  • [Best algorithm to count the number of set bits in a 32-bit integer?][1] [1]: http://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer/5469563#5469563 – Robert S. Barnes Feb 16 '12 at 05:23

1 Answers1

6

This is a method I know of for doing this, it will only iterate for the number of bits set in v, at the end of execution c will hold the number of bits in v:

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

source: C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie)

example: 

v = 1010; //2 bits are set
v - 1 = 1010(10 decimal) - 1 = 1001(9 decimal)

1010
1001 &
------
1000         The least significant bit is unset, c is incremented by 1

v = 1000 
v - 1 = 1000 - 1 = 0111

1000
0111 &
-------
0000         The least significant bit is unset again, c is incremented 
             by 1, the loop stops because there are no more set bits.
Hunter McMillen
  • 59,865
  • 24
  • 119
  • 170