What is an efficient way to get the least non-negative residue modulo n in C?

Is there an efficient way to get the least non-negative residue modulo n, where n is positive, in C?

This is quite easy if the number is non-n开发者_如何转开发egative, then it's just a % n (where a is the non-negative integer).

However when a is negative, it appears the behaviour, in C89, is implementation defined (thanks kennyTM). I.e. -2 % 11 = -2 or 9.

You could simply check if the result is negative and then act accordingly:

int mod(int n, int m) {
   int r = n % m;
   if (r < 0)
      return r + m;
   else
      return r;
}

Or, without if-then-else and as a single expression:

r = ((n % m) + m) % m;

Furthermore, in C99 the behaviour is defined to be the annoying one: -2 % 11 = -2.

In general (i.e., n % m when m is not constant and the range of n is unconstrained), you probably can't do better than the usual

res = ((n % m) + m) % m

It may be interesting to compare that to the following on your platform; one branch might win against the extra modulo:

res = n % m;
if (res < 0)  res += m;

How about

if (a > 0)
    return a % n;
if (a < 0)
{
    r = n - (-a % n);
    if (r == n)
        return 0;
    return r;
}

If a < 0, then r = -a % n is a value in [0, n) such that k * n + r = -a for some integer k. Then n - r is a value in (0, n], and since -r = a + k * n, we have n - r = a + (k + 1) * n, or a = (n - r) + (-k - 1) * n. From this you can see that n - r is the modulus of a, and since it is in (0, n], it is non-negative.

Finally, you want the result to be in the range [0, n), not in (0, n]. To ensure this, we check if r is n, and if so, return 0. (Which is of course modulus-n-equivalent to n)

Few processors implement remainder in hardware, rather it's synthesized from a division and a multiplication. So this is not really a cumbersome reimplementation from the machine's standpoint:

int qm = n / m * m; // a positive or negative multiple of m, rounded up or down
if ( qm <= n ) return n - qm; // usual definition of %
else return n - qm + m; // most common definition of -%, with adjustment

Micro-optimization of the conditional + may also be beneficial. This could be faster or slower on your machine, but it will work:

int rem = n - n / m * m;
return rem + m & -( rem < 0 );

Total cost: one regular modulo plus one right-shift (to generate -(rem<0)), one bitwise and, and one add.