Path: utzoo!mnetor!uunet!mcvax!guido
From: guido@cwi.nl (Guido van Rossum)
Newsgroups: comp.sys.mac.programmer
Subject: Counting bits (was Re: Polygon question)
Message-ID: <250@piring.cwi.nl>
Date: 26 Mar 88 18:52:32 GMT
References: <24153@brunix.UUCP> <104700016@uiucdcsp>
Reply-To: guido@cwi.nl (Guido van Rossum)
Organization: The Royal Society for Prevention of Cruelty to Amoebae
Lines: 43

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.  Similar tricks are useful for any
code that looks at data one bit at a time (see the fast CRC computing
code in xbin version 3.4a that I once posted on the net(though I didn't
write it)).

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

static char nbits[256]= {
#include "nbits.h" /* See below */
};

/* Count one-bits in n-byte array p. */

long
bitcount(p, n)
	unsigned char *p;
	int n;
{
	long total= 0;
	while (--n >= 0)
		total += nbits[*p++];
	return total;
}

where the file "bits.h" is generated by the following program:

main()
{
	int i;
	for (i= 0; i < 256; ++i) {
		int n= 0, j= i;
		while (j != 0) {
			if (j&1) ++n;
			j= (j&~1) >> 1;
		}
		printf("%d, ", n);
		if (i%16 == 15)
			printf("\n");
	}
}