Path: utzoo!attcan!uunet!nih-csl!lhc!mimsy!chris
From: chris@mimsy.umd.edu (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: count of bits set in a long
Message-ID: <26745@mimsy.umd.edu>
Date: 27 Sep 90 21:26:47 GMT
References: <37545@ut-emx.uucp> <3820@goanna.cs.rmit.oz.au> <34281@cup.portal.com> <2859@litchi.bbn.com>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 21

In article <2859@litchi.bbn.com> rsalz@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@cs.umd.edu	Path:	uunet!mimsy!chris