Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!apple!agate!linus!linus!bs
From: bs@linus.mitre.org (Robert D. Silverman)
Newsgroups: comp.lang.c
Subject: Re: % operator (was Re: count of bits set in a long)
Message-ID: <121784@linus.mitre.org>
Date: 1 Oct 90 15:32:15 GMT
References: <37545@ut-emx.uucp> <3820@goanna.cs.rmit.oz.au> <34281@cup.portal.com> <2859@litchi.bbn.com> <51467@brunix.UUCP> <3417@gmdzi.gmd.de>
Reply-To: bs@gauss.UUCP (Robert D. Silverman)
Organization: The MITRE Corporation, Bedford MA
Lines: 36

In article <3417@gmdzi.gmd.de> wittig@gmdzi.gmd.de (Georg Wittig) writes:
>tac@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"