Best way to make Java's modulus behave like it should with negative numbers?

Question

It behaves as it should a % b = a - a / b * b; i.e. it's the remainder.

You can do (a % b + b) % b

---

This expression works as the result of (a % b) is necessarily lower than b, no matter if a is positive or negative. Adding b takes care of the negative values of a, since (a % b) is a negative value between -b and 0, (a % b + b) is necessarily lower than b and positive. The last modulo is there in case a was positive to begin with, since if a is positive (a % b + b) would become larger than b. Therefore, (a % b + b) % b turns it into smaller than b again (and doesn't affect negative a values).

As of Java 8, you can use Math.floorMod(int x, int y) and Math.floorMod(long x, long y). Both of these methods return the same results as Peter's answer.

Math.floorMod( 2,  3) =  2
Math.floorMod(-2,  3) =  1
Math.floorMod( 2, -3) = -1
Math.floorMod(-2, -3) = -2

For those not using (or not able to use) Java 8 yet, Guava came to the rescue with IntMath.mod(), available since Guava 11.0.

IntMath.mod( 2, 3) = 2
IntMath.mod(-2, 3) = 1

One caveat: unlike Java 8's Math.floorMod(), the divisor (the second parameter) cannot be negative.

In number theory, the result is always positive. I would guess that this is not always the case in computer languages because not all programmers are mathematicians. My two cents, I would consider it a design defect of the language, but you can't change it now.

=MOD(-4,180) = 176 =MOD(176, 180) = 176

because 180 * (-1) + 176 = -4 the same as 180 * 0 + 176 = 176

Using the clock example here, http://mathworld.wolfram.com/Congruence.html you would not say duration_of_time mod cycle_length is -45 minutes, you would say 15 minutes, even though both answers satisfy the base equation.

Java 8 has Math.floorMod, but it is very slow (its implementation has multiple divisions, multiplications, and a conditional). Its possible that the JVM has an intrinsic optimized stub for it, however, which would speed it up significantly.

The fastest way to do this without floorMod is like some other answers here, but with no conditional branches and only one slow % op.

Assuming n is positive, and x may be anything:

int remainder = (x % n); // may be negative if x is negative
//if remainder is negative, adds n, otherwise adds 0
return ((remainder >> 31) & n) + remainder;

The results when n = 3:

x | result
----------
-4| 2
-3| 0
-2| 1
-1| 2
 0| 0
 1| 1
 2| 2
 3| 0
 4| 1

If you only need a uniform distribution between 0 and n-1 and not the exact mod operator, and your x's do not cluster near 0, the following will be even faster, as there is more instruction level parallelism and the slow % computation will occur in parallel with the other parts as they do not depend on its result.

return ((x >> 31) & (n - 1)) + (x % n)

The results for the above with n = 3:

x | result
----------
-5| 0
-4| 1
-3| 2
-2| 0
-1| 1
 0| 0
 1| 1
 2| 2
 3| 0
 4| 1
 5| 2

If the input is random in the full range of an int, the distribution of both two solutions will be the same. If the input clusters near zero, there will be too few results at n - 1 in the latter solution.

Here is an alternative:

a < 0 ? b-1 - (-a-1) % b : a % b

This might or might not be faster than that other formula [(a % b + b) % b]. Unlike the other formula, it contains a branch, but uses one less modulo operation. Probably a win if the computer can predict a < 0 correctly.

(Edit: Fixed the formula.)