Path: utzoo!attcan!uunet!mcvax!aeb
From: aeb@cwi.nl (Andries Brouwer)
Newsgroups: comp.unix.questions
Subject: Re: Bit counting
Message-ID: <7825@boring.cwi.nl>
Date: 15 Jan 89 17:40:37 GMT
References: <1207@ncar.ucar.edu>
Organization: CWI, Amsterdam
Lines: 23

In article <1207@ncar.ucar.edu> thor@thor.ucar.edu (Rich Neitzel)
gave a number of algorithms of which his `bit pair addition' was
the fastest. My favourite routine is the following:

	/* find number of 1-bits in a */
	bitcnt(a) register int a; {
	register int ct = 0;
		while(a){
			a &= (a-1);
			ct++;
		}
		return(ct);
	}

It is twice as fast on the average as the usual bit count versions,
and comparable in speed to Neitzels routine (but much shorter).
An important advantage is that it does not depend on the word size.
Timing results:                this routine    Neitzels
        VAX 200000 iterations    12 sec         10 sec
     HARRIS 800000 iterations     7 sec         12 sec

-- 
      Andries Brouwer -- CWI, Amsterdam -- uunet!mcvax!aeb -- aeb@cwi.nl