% operator (was Re: count of bits set in a long)

[Karl Heuer]

In article <121784 at linus.mitre.org> bs at gauss.UUCP (Robert D. Silverman) writes:
>Here's a simple, well known trick for computing x mod (2^n-1) when x > 0.
>let x = a*2^n + b,  that is partition x into lower and upper n bits...

Note the unstated assumption that x is at most 2n bits wide.  This wasn't true
in the original context.  It can be fixed by iterating the procedure--in fact
this is where that mod came from in the first place: it replaces one or two
folding operations in the modless form of the algorithm.  (Presumably the
original algorithm was being optimized for codespace instead of time, or was
being done on a machine where mod was cheap.)

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