Richbits

Counting bits

How do you count bits?

Peter Wegner published a technique in the Communications of the ACM, Vol. 3 No. 5, Page 322 on May 1960 for doing so. The article is available here and has the doi 10.1145/367236.367286.

//Counts the number of bits that are "on"
//This is a method developed by Peter Wegner (doi: 10.1145/367236.367286)
template<class T>
T countbits(T a){
  unsigned int c; // c accumulates the total bits set in combined
  for (c = 0; a; ++c)
    a &= a - 1;   // clear the least significant bit set
  return c;
}