count of bits set in a long

[Chris Torek]

In article <2859 at litchi.bbn.com> rsalz at bbn.com (Rich Salz) posts the
`hackmem 169' technique for counting set bits in a 32 bit word:
>	y = (mask >> 1) &033333333333;
>	y = mask - y - ((y >>1) & 033333333333);
>	return (((y + (y >> 3)) & 030707070707) % 077);

This is similar to one of the methods summarized earlier, which also
used remainders (63 here, 255 there).  Note that remainder (`%') is
a `heavy' operation on many computers---you can typically do anywhere
from four to a several dozen `regular' instructions in the time it
takes to compute a remainder.  One of the other methods is therefore
likely to be faster.

(The nice thing about the `x &= x-1' loop is that it is independent of
the word size, and only runs for as many bits as are set.  For a 32 bit
word and a random distribution, that is 16 iterations average, so the
look-up-each-byte version is likely to be faster, requiring only four
table lookups and three additions.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 405 2750)
Domain:	chris at cs.umd.edu	Path:	uunet!mimsy!chris