Path: utzoo!mnetor!uunet!husc6!uwvax!rutgers!iuvax!pur-ee!uiucdcs!uiucdcsp!gillies
From: gillies@uiucdcsp.cs.uiuc.edu
Newsgroups: comp.sys.mac.programmer
Subject: Re: Polygon question
Message-ID: <104700016@uiucdcsp>
Date: 25 Mar 88 23:40:00 GMT
References: <24153@brunix.UUCP>
Lines: 44
Nf-ID: #R:brunix.UUCP:24153:uiucdcsp:104700016:000:1474
Nf-From: uiucdcsp.cs.uiuc.edu!gillies    Mar 25 17:40:00 1988


If you want to count the bits in a bitmap, it's going to be slow, but
you can be clever and speed things up quite a bit

- 1.  Loop through all the computer words in the bitmap.  Use the
largest word-size possible (32-bits).  Skip over words that are zero.

- 2.  For non-zero N-bit (32-bit) words, you can count the bits in
parallel using LogN (5) steps.  For details, see "Combinatorial
Algorithms", chapter 1, but Reingold, Nievergelt, Deo.  Briefly, in C,
it might look like:

bitsum(X)
long unsigned X;
{	long unsigned Y, Z;
#define Mask1		025252525252	/* every other bit */
#define NotMask1	~Mask1
#define Mask2		031463146314	/* 2 bits on, 2 bits off */
#define NotMask2	~Mask2
...
	Y = (X & Mask1) >> 1;		/* step 1 */
        Z = (X & NotMask1);
	X = Y + Z;

	Y = (X & Mask2) >> 2;		/* step 2 */
	Z = (X & NotMask2);
	X = Y + Z;
	/* step 3:  4 bits on, 4 bits off, shift by 4 */
	/* step 4:  8 bits on, 8 bits off, shift by 8 */
	/* step 5: 16 bits on, 16 bits off, shift by 16 -- Done */

	/* for efficiency, don't use vars Y & Z, compress this
	   subroutine into 5 assignments to the X variable, e.g.
	   X = (X & NotMask1) + ((X & Mask1) >> 1);
	 */
}

Essentially, you are adding up all the bits in parallel.  The first
step does 16 single-bit adds in parallel.  The second step does 8
double-bit adds in parallel.  The third step does 4 quad-bit adds in
parallel, and so on.

Don Gillies {ihnp4!uiucdcs!gillies} U of Illinois
            {gillies@p.cs.uiuc.edu}