Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!hanami!landman
From: landman%hanami@Sun.COM (Howard A. Landman)
Newsgroups: comp.lang.misc
Subject: Re: Clever programming tricks wanted
Message-ID: <85188@sun.uucp>
Date: 13 Jan 89 07:28:51 GMT
References: <4061@hubcap.UUCP>
Sender: news@sun.uucp
Reply-To: landman@sun.UUCP (Howard A. Landman)
Organization: Sun Microsystems, Mountain View
Lines: 38

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      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;
	/* 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