Effectively calculate modulo the sum of two numbers

Question

I have three N bit numbers, A , B and C I cannot easily calculate (A + B) % C , but I can easily calculate A % C and B % C If the modulo operation is unsigned and I know in advance that A + B does not wrap the N bit, then I can calculate ((A % C) + (B % C)) % C However, is it possible to do something for cases where the modulo operation is signed or the addition of A and B can lead to a wrapper.

There seems to be some confusion as to why ((A % C) + (B % C)) % C cannot be relied on to always work. Here is an unsigned example:

 unsigned A = 0x1U; unsigned B = 0xFFFFFFFFU; unsigned C = 0x3U; ((A % C) + (B % C)) % C == 0x1U but (A + B) % C == 0x0U 

Here is an example:

 int A = 0x1; int B = 0xE27F9803; int C = 0x3U; ((A % C) + (B % C)) % C == 0x1U but (A + B) % C == -2 

Answer 1

What would you like:

 ((a+b)%2^n)%c 

Let be

 a+b = k 2^n + d 

Where k = 0 or 1 and d < 2^n .

Turning on:

  ((k 2^n + d) % 2^n) % c = (d % 2^n) % c = d % c 

Taking the previous expression modulo c , you get

  (a + b) % c = (k 2^n + d) % c => d % c = a % c + b % c - k 2^n % c 

With n = 32 , in C:

 unsigned myMod(unsigned a, unsigned b, unsigned c) { // k = 1 if the sum overflows unsigned k = ( a > UINT_MAX - b or b > UINT_MAX - a); return ( a % c + b % c - k*(UINT_MAX%c + 1))%c; } myMod(0x1U,0xFFFFFFFFU,0x3U) == 0 

Answer 2

In mathematics, integer division is usually rounded down to negative infinity, and the modulo sign is the same as the “divider”, or it is equal to zero: -10 mod 3 = 2 and 10 mod -3 = -2 (the coefficient is rounded to - 4). In C / C ++, integer division is rounded to zero, and the% sign coincides with the sign "dividend" or "numerator" or equal to zero, -10 mod 3 = -1 and 10 mod -3 = 1 (the factor is rounded to zero to - 3). When performing a mathematical model of the final field with C / C ++, you need to perform corrections for corrections so that the results meet the mathematical definition of modulo. For example, if X% 3 = -1, add 3 so that X mod 3 = +2.

Assuming C is positive, a mathematical field modulo C consists of the numbers {0, 1, ... C-1} without any negative numbers. If C is negative (this is unusual for modulo), then the field is {0, -1, -2, ... C + 1}. Assuming C is positive, then if A or B is negative, then you can still use ((A% C) + (B% C))% C and then send the correct answers if the result is negative by adding C to the result .