Search code examples
coverflowmodulounsigned-integer

C Programming - using modulo of a sum of unsigned integers which overflows

I have an assignment in University, where I need to write functions for a given main program. It is all in c.

So, my problem is that I need to use the module of a sum of two unsigned integers. 

uint32_t mod_add(uint32_t x, uint32_t y, uint32_t n)
{
    uint32_t res;

    res = (x + y) % n;

This works fine, when sum of x and y is below 2^32-1. My trouble is that when the sum is above this value, it obviously overflows and the modulo value is wrong.

In my assignment x = 2^32-3; y =1174501 and n =2^32-1 (n is the modulo); My result is 1174497, it should be 1174499.

Anybody any idea, how to solve this?

Solution

  • Here you are.

    uint32_t remainder(uint32_t x, uint32_t y, uint32_t d)
{
    uint32_t r1 = x % d;
    uint32_t r2 = y % d;

    return r1 < (d - r2) ? r1 + r2 : r1 - (d - r2);
}

    Of course instead of uint32_t you can use any integer type as for example unsigned long long.