🚀 go-pugleaf

In article <85188@sun.uucp> landman@sun.UUCP (Howard A. Landman) writes:
.In article <4061@hubcap.UUCP> mcvax!etive.ed.ac.uk!gvw@uunet.UU.NET (MOBY) writes:
.>I would like to hear about similar tricks that people have invented/
.>discovered.  In particular, I'm looking for fast ways to count the
.>number of 1 bits in a word (on machines that don't have this as a
.>machine instruction :-)
.
.int CountBitsInWord(rw)
|int CountBitsInWord(arg)
.int      rw;
|int      arg;
.{
.int      tmp;
|unsigned long      tmp, rw = (unsigned long) arg & 0xFFFFFFFF;
.	/* This uses a clever algorithm I picked up somewhere.  */
.	/* Try a few examples and you'll see why it works.      */
.	/* Phase 1 - add up pairs of bits. */
.	tmp = rw & 0xAAAAAAAA;
.	rw &= 0x55555555;
.	rw += tmp >> 1;
.	/* Phase 2 - add up 2-bit sums to get 3-bit sums in 4 bits. */
.	tmp = rw & 0xCCCCCCCC;
.	rw &= 0x33333333;
.	rw += tmp >> 2;
.	/* Phase 3 - add up 3-bit sums to get 4-bit sums in 8 bits. */
.	tmp = rw & 0xF0F0F0F0;
.	rw &= 0x0F0F0F0F;
.	rw += tmp >> 4;
.	/* Phase 4 - add up 4-bit sums to get 5-bit sums in 16 bits. */
.	tmp = rw & 0xFF00FF00;
.	rw &= 0x00FF00FF;
.	rw += tmp >> 8;
.	/* Phase 5 - add up 5-bit sums to get 6-bit sum in 32 bits. */
.	tmp = rw; /* & 0xFFFF0000 not needed due to shift below */
.	rw &= 0x0000FFFF;
.	rw += tmp >> 16;
.	/* All done. */
.	return (int) rw;
.}
.
.	Howard A. Landman
.	landman@hanami.sun.com

On some machines, right shift of signed integers proprogates the sign bit.
Also, on some machines an int is not at least 32 bits;

	Randolph J. Herber, Amdahl Sr Sys Eng, ..!att!ihlpa!rjh,
	(312) 979-6553, IH 6X213, AT&T Bell Labs, Naperville, IL 60566
	@ home: {att|amdahl|mcdchg|clout|obdient}!yclept!{rjh|root}