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

[Risto Lankinen]

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
>	literature? Is the following true?
>	
>		x % n = (x%(n+1) + floor(x/(n+1))) % n	      (n != 0;n != -1)
>	
>	Do there exist similar "surprising" equations?

Hi!

Not in attempt to 'prove' anything, but ...

Let 'x' be of form 'X*2^k + x' (where X and x are distinguished and x is
less than 2^k).  Subtract 'X*(2^k-1)' to get 'x+X' which will have the same
remainder as the original formula, when divided by '2^k-1' .

Were the X greater than 2^k-1 , the same procedure could be repeated until
the remaining sum of 'hi- and lo-parts' becomes less than 2^k-1

This works in decimal base, too.  For example, 147 MOD 9 = (14+7) MOD 9 =
21 MOD 9 = (2+1) MOD 9 = 3 .  There's a similar formula for modulus '2^k+1' .

By the way, when 'k=0' in '2^k-1' , this reduces to a 'x MOD 1' , which is
how the parity bit is calculated in a binary number.  Has anyone got more
to tell about the mathematics involved in parity function?

Terveisin: Risto Lankinen
-- 
Risto Lankinen / product specialist ***************************************
Nokia Data Systems, Technology Dept *  2                              2   *
THIS SPACE INTENTIONALLY LEFT BLANK * 2 -1 is PRIME!  Now working on 2 +1 *
replies: risto at yj.data.nokia.fi     ***************************************