Path: utzoo!attcan!uunet!lll-winken!lll-ncis!helios.ee.lbl.gov!pasteur!agate!bionet!csd4.milw.wisc.edu!nic.MR.NET!xanth!ukma!gatech!ncsuvx!mcnc!rti!trt
From: trt@rti.UUCP (Thomas Truscott)
Newsgroups: comp.lang.misc
Subject: Re: Clever programming tricks wanted
Summary: use multiply to add up the sums
Message-ID: <2721@rti.UUCP>
Date: 13 Jan 89 16:42:40 GMT
References: <4061@hubcap.UUCP> <85188@sun.uucp>
Organization: Research Triangle Institute, RTP, NC
Lines: 50

In article <85188@sun.uucp>, landman%hanami@Sun.COM (Howard A. Landman) writes:
> In article <4061@hubcap.UUCP> mcvax!etive.ed.ac.uk!gvw@uunet.UU.NET (MOBY) writes:
> > ...  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 :-)

If your machine has a fast integer multiply,
it can be used as follows:

: int CountBitsInWord(rw)
: int      rw;
: {
: int      tmp;
: 	/* 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;
#ifdef MULTIPLY
	/* Phase 4,5 add up sums */
	rw = (rw * 0x01010101) >> 24;
#else
: 	/* 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;
#endif
: 	/* All done. */
: 	return (int) rw;
: }

If the count is guaranteed never to exceed 15 then phases 3,4,5
can be done with "rw = ((unsigned)(rw * 0x11111111)) >> 28;"
I thought of this trick (as did others, no doubt) a decade
ago when working on a computer chess program.
But we never used it since table lookup seemed faster yet.
	Tom Truscott