BIT Counting: C programming problem

[Joe Buck]

Bernie Cosell's simple bit-counting algorithm can easily be demonstrated
to be correct, and the basic idea can be used in other ways (I've used it
in a tiny little real-time O/S for a DSP chip to allocate event flags).


int BitCount(num)
int num;
{
     int count = 0;
     while (num != 0) {
 	num &= num-1;
	count += 1;
     }
     return count;
}

Given an integer N, what is N & (N-1), where "&" is the bitwise AND operation?
It is a word identical to N, except that the least significant "1" bit is
cleared.  So the result of the operation has one fewer bit set, and
for a number with M "1" bits, repeating the operation M times reduces the
result to zero.

So here's a picture to show how it works.  Let's say N has the pattern

N       = XXXXXX10000
N-1     = XXXXXX01111
N&(N-1) = XXXXXX00000 

and the least significant bit is cleared.

In the application I referred to, I had 32 global event flags, represented
as bits in a word.

alloc_evf ()
{
   int tmp, evf;

   if (AvailEvents != 0) {
       tmp = AvailEvents & (AvailEvents - 1);
       evf = AvailEvents - tmp;
       AvailEvents = tmp;
   }
   else ERROR; /* no event flags available */
}   
-- 
- Joe Buck	jbuck at epimass.epi.com, or uunet!epimass.epi.com!jbuck,
		or jbuck%epimass.epi.com at uunet.uu.net for old Arpa sites
I am of the opinion that my life belongs to the whole community, and as long
as I live it is my privilege to do for it whatever I can.  -- G. B. Shaw