Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!apple!snorkelwacker!mintaka!spdcc!ima!haddock!karl
From: karl@haddock.ima.isc.com (Karl Heuer)
Newsgroups: comp.lang.c
Subject: Re: SUMMARY: count of bits set in a word
Keywords: bits set, count of, long
Message-ID: <18304@haddock.ima.isc.com>
Date: 28 Sep 90 20:15:35 GMT
References: <37678@ut-emx.uucp> <6476@wolfen.cc.uow.oz>
Reply-To: karl@kelp.ima.isc.com (Karl Heuer)
Organization: Interactive Systems, Cambridge, MA 02138-5302
Lines: 24

In article <6476@wolfen.cc.uow.oz> pejn@wolfen.cc.uow.oz (Paul Nulsen) writes:
>nwagner@ut-emx.uucp (Neal R. Wagner) writes:
>          The fastest solutions fell into three categories:
>            i = (i & 0x55555555) + ((i>>1) & 0x55555555);
>            i = (i & 0x33333333) + ((i>>2) & 0x33333333);
>            i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F);
>            return (i % 255);
>
>Too cryptic I fear. This will only count the bottom 8 bits (try it on
>0x101).

I did; works fine.  I think you misread the last expression as "i & 255" or
"i % 256" when it's actually "i % 255 /* casting out 255s */".

Your suggestion of adding two more folds may indeed be useful, though, if "%"
is a sufficiently expensive operation.

(Somebody else suggested that the "%" operation can be eliminated in favor of
a loop.  This isn't necessary, since in either the %63 or %255 case the
algorithm can be extended by another step or two to yield the complete answer;
the only reason for using mod is to bum a few instructions.  And the whole
point of the exercise was to get rid of the loop.)

Karl W. Z. Heuer (karl@kelp.ima.isc.com or ima!kelp!karl), The Walking Lint