equivalent expressions

Question

I'm trying to figure out an equivalent expressions of the following equations using bitwise, addition, and/or subtraction operators. I know there's suppose to be an answer (which furthermore generalizes to work for any modulus 2^a-1, where a is a power of 2), but for some reason I can't seem to figure out what the relation is.

Initial expressions:

x = n % (2^32-1);
c = (int)n / (2^32-1); // ints are 32-bit, but x, c, and n may have a greater number of bits

My procedure for the first expression was to take the modulo of 2^32, then try to make up the difference between the two modulo's. I'm having trouble on this second part.

x = n & 0xFFFFFFFF + difference // how do I calculate difference?

I know that the difference n%(2^32)-n%(2^32-1) is periodic (with a period of 2^32*(2^32-1)), and there's a "spike up' starting at multiples of 2^32-1 and ending at 2^32. After each 2^32 multiple, the difference plot decreases by 1 (hopefully my descriptions make sense)

Similarly, the second expression could be calculated in a similar fashion:

c = n >> 32 + makeup // how do I calculate makeup?

I think makeup steadily increases by 1 at multiples of 2^32-1 (and decreases by 1 at multiples of 2^32), though I'm having troubles expressing this idea in terms of the available operators.

Unknown Unknown · Accepted Answer · 2011-04-23T22:42:19

You can use these identities:

n mod (x - 1) = (((n div x) mod (x - 1)) + ((n mod x) mod (x - 1))) mod (x - 1)
n div (x - 1) = (n div x) + (((n div x) + (n mod x)) div (x - 1))

First comes from (ab+c) mod d = ((a mod d) (b mod d) + (c mod d)) mod d.

Second comes from expanding n = ax + b = a(x-1) + a + b, while dividing by x-1.

equivalent expressions

2 Answers