count of bits set in a long

[VanZandt]

tac at cs.brown.edu (Theodore A. Camus) writes...
> As chris at 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