Bit counting

[Leo de Wit]

In article <7825 at boring.cwi.nl> aeb at cwi.nl (Andries Brouwer) writes:
|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

But the speed DOES depend on the number of bits set in the integer!
Each iteration of the loop removes and counts the least significant
bit, so this means 32 iterations on a unsigned int, 32 bits wide, with
all bits set. In this particular situation, it may well end up being
slower than an ordinary shift-&-count-until-zero.

What input data were used for those timing results???

	  Leo.