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

[Robert D. Silverman]

In article <3417 at gmdzi.gmd.de> wittig at gmdzi.gmd.de (Georg Wittig) writes:
>tac at cs.brown.edu (Theodore A. Camus) writes:
>
>>However, 077 in octal is 63 in decimal, and I believe the following
>					     ^^^^^^^^^
>>relationship is true : x % 63 = [(x % 64) + (x / 64)] % 63
>
>	Does there exist a proof for that equation? Can it be found in

Here's a simple, well known trick for computing x mod (2^n-1) when x > 0.
If x is less than 0, make it positive first, then negate the final result.

let x = a*2^n + b,  that is partition x into lower and upper n bits.

Then:

x = a*(2^n-1) + a + b

So:

x mod (2^n-1) = a + b.


Let mask[n] be a mask representing the lowest n bits all lit.

Then we have

x mod (2^n-1) = (x & mask[n]) + (x >> n)

This is one add, one logical bitwise and, and one shift.

-- 
Bob Silverman
#include <std.disclaimer>
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"