SUMMARY: count of bits set in a word

[Karl Heuer]

In article <6476 at wolfen.cc.uow.oz> pejn at wolfen.cc.uow.oz (Paul Nulsen) writes:
>nwagner at 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 at kelp.ima.isc.com or ima!kelp!karl), The Walking Lint