c - Efficiently compute the modulo of the sum of two numbers -

i have 3 n-bit numbers, a, b, , c. cannot calculate (a + b) % c can calculate a % c , b % c. if modulo operation unsigned , know ahead of time a + b not wrap around n bits can instead calculate ((a % c) + (b % c)) % c. however, possible cases modulo operation signed or addition of a , b might lead wrap-around.

it looks there might confusion why ((a % c) + (b % c)) % c cannot relied upon work. here unsigned example:

unsigned = 0x1u; unsigned b = 0xffffffffu; unsigned c = 0x3u; ((a % c) + (b % c)) % c == 0x1u (a + b) % c == 0x0u 

here signed example:

int = 0x1; int b = 0xe27f9803; int c = 0x3u; ((a % c) + (b % c)) % c == 0x1u (a + b) % c == -2 

what want is:

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

let

a+b = k 2^n + d 

where k = 0 or 1 , d < 2^n.

plugging in get:

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

taking previous expression modulo c get

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

with n = 32, in c:

unsigned mymod(unsigned a, unsigned b, unsigned c) {      // k = 1 if sum overflows      unsigned k = ( > uint_max - b or b > uint_max - a);       return ( % c + b % c -  k*(uint_max%c + 1))%c; }  mymod(0x1u,0xffffffffu,0x3u) == 0