[comp.sys.mac.programmer] Counting bits

guido@cwi.nl (Guido van Rossum) (03/27/88)

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");
	}
}

guido@cwi.nl (Guido van Rossum) (03/27/88)

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