Path: utzoo!utgpu!water!watmath!clyde!att-cb!osu-cis!tut.cis.ohio-state.edu!mailrus!umix!uunet!mcvax!guido
From: guido@cwi.nl (Guido van Rossum)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Counting bits (was Re: Polygon question)
Message-ID: <251@piring.cwi.nl>
Date: 26 Mar 88 20:07:38 GMT
References: <24153@brunix.UUCP> <104700016@uiucdcsp> <250@piring.cwi.nl>
Reply-To: guido@cwi.nl (Guido van Rossum)
Organization: The Royal Society for Prevention of Cruelty to Amoebae
Lines: 34

In article <250@piring.cwi.nl> I wrote:
>Counting bits is better done by using a look-up table.  I did a quick
>test of the code below and found it was 25 to 30 (!) times faster than the
>LogN method explained by Don Gilles.

Well, I jumped too fast.  My method is faster, but by a factor of 1.5 or 2.

BTW, here's the C code for Don's code I used:

long alt_bcount(cp, n)
	unsigned char *cp;
	int n;
{
	long total= 0;
	unsigned long *p= (unsigned long *)cp;
	
	n /= sizeof(long);
	
	while (--n >= 0) {
		register unsigned long x= *p++;
		if (x == 0)
			continue;
		x= (x & 0x55555555) + ((x>>1) & 0x55555555);
		x= (x & 0x33333333) + ((x>>2) & 0x33333333);
		x= (x & 0x0f0f0f0f) + ((x>>4) & 0x0f0f0f0f);
		x= (x & 0x00ff00ff) + ((x>>8) & 0x00ff00ff);
		total += (x & 0x0000ffff) + ((x>>16) & 0x0000ffff);
	}
	
	return total;
}
--
Guido van Rossum, Centre for Mathematics and Computer Science (CWI), Amsterdam
guido@cwi.nl or mcvax!guido or (from ARPAnet) guido%cwi.nl@uunet.uu.net