Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!agate!linus!linus!sdimax2!jrv
From: jrv@sdimax2.mitre.org (VanZandt)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Message-ID: <121785@linus.mitre.org>
Date: 1 Oct 90 15:49:54 GMT
References: <37545@ut-emx.uucp> <3820@goanna.cs.rmit.oz.au> <34281@cup.portal.com> <2859@litchi.bbn.com> <51467@brunix.UUCP>
Sender: usenet@linus.mitre.org
Lines: 38

tac@cs.brown.edu (Theodore A. Camus) writes...
> As chris@mimsy.umd.edu noted, '%' is usually a costly operation.
> However, 077 in octal is 63 in decimal, and I believe the following
> relationship is true : x % 63 = [(x % 64) + (x / 64)] % 63 ...

The corresponding algorithm for finding x%9 in the decimal world is
known as "casting out nines".

> ...and can be efficiently calculated by : 
...
>        if (x = 63)
               ^ should be ==
>          return 0 
                   ^ needs ;

The function is then...

bitcount(unsigned long mask)
{	unsigned long y;
	
	y = (mask >> 1) &033333333333L;
	y = mask - y - ((y >>1) & 033333333333L);
	y = (y + (y >> 3)) & 030707070707L;

			/* find y%077 using the relation 
				y % 077 = [(y % 0100) + (y / 0100)] % 077 */
	while (y > 077) {				/* 2 assembly instructions */
		y =  (y & 077)+(y >> 6);	/* 3 assembly instructions */
		}
	if (y == 077)					/* 1 assembly instruction  */
		return 0;					/* 1 assembly instruction  */
	else							/* fall through, take value of y */
		return y;					/*    =  0 instructions   */
}

Would the corresponding algorithm using 255 rather than 63 be faster?

                           - Jim Van Zandt