Xref: utzoo comp.lang.c:15454 comp.std.c:671
Path: utzoo!attcan!uunet!lll-winken!ames!mailrus!tut.cis.ohio-state.edu!bloom-beacon!apple!epimass!jbuck
From: jbuck@epimass.EPI.COM (Joe Buck)
Newsgroups: comp.lang.c,comp.std.c
Subject: Re: BIT Counting: C programming problem
Message-ID: <2787@epimass.EPI.COM>
Date: 12 Jan 89 19:05:59 GMT
References: <34389@bbn.COM) <1171@goofy.megatest.UUCP> <755@infmx.UUCP>
Reply-To: jbuck@epimass.EPI.COM (Joe Buck)
Organization: Entropic Processing, Inc., Cupertino, CA
Lines: 49

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@epimass.epi.com, or uunet!epimass.epi.com!jbuck,
		or jbuck%epimass.epi.com@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