Bit counting

[Andries Brouwer]

In article <1207 at ncar.ucar.edu> thor at 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 at cwi.nl