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

Question

In java when you do

a % b

If a is negative, it will return a negative result, instead of wrapping around to b like it should. What's the best way to fix this? Only way I can think is

a < 0 ? b + a : a % b

Segalman

There's no "right" modulus behaviour when dealing with negative numbers - a lot of languages do it this way, a lot of languages do it different, and a few languages do something completely different. At least the first two have their pros and cons. – Hiatus

this is just weird for me. i thought it should only return negative if b is negative. – Segalman

possible duplicate of How does java do modulus calculations with negative numbers? – Medea

it is. but the title of that question should be renamed. i wouldn't click that question if i was searching for this one because i already know how java modulus works. – Segalman

I just renamed it to that from "Why is -13 % 64 = 51?", which would never in a million years be anything someone would search on. So this question title is much better, and much more searchable on keywords like modulus, negative, calculation, numbers. – Medea

Java doesn't have a modulus operator. The operator that many programmers mistakenly call modulus is actually called the remainder operator, which hints at why it behaves as it does. – Isochronize

Answer 1

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).

Griffis

this works better thanks. and it works for negative numbers that are much larger than b too. – Segalman

this is a really good answer! as close to elegant as java will let you go, I think – Osi

@PeterLawrey - Thanks, I needed this solution too, but would you be willing to explain why it works? – Giese

It works since 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 lower than b and lower than 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). – Semanteme

@eitanfar I've included your excellent explanation into the answer (with a minor correction for a < 0, maybe you could have a look) – Lancet

I just saw this commented on another question regarding the same topic; It might be worth mentioning that (a % b + b) % b breaks down for very large values of a and b. For example, using a = Integer.MAX_VALUE - 1 and b = Integer.MAX_VALUE will give -3 as result, which is a negative number, which is what you wanted to avoid. – Dagmardagna

Isnt (a % b + b) % b much slower to execute than a = a % b; while (a < 0) { a += b;} ? Since you have to do two modulus operations? (Assuming that you're only interested in cases where a <= b) – Ulphiah

@Ulphiah using a while would be slower if you really need it except you only need an if in which case it is actually faster. – Griffis

What about including a solution (without a conditional) for those who also need the quotient from the modulo division (such that, for example, -1 div 4 = -1, instead of -1 / 4 = 0)? Here it is (assuming you already have the modulus in variable mod_ab): (a - (mod_ab - a % b)) / b. – Fishplate

One small note: If a is within b distance from 0 (e.g. when doing screen wrapping of some updated x-coordinate a within a 2D game map of width b), (a + b) % b will do. – Consternation

Pretty sure modulo and remainder are not the same thing. You can look up the definitions in a math reference, but % means modulo in some languages and remainder in others. #40692516 – Guacharo

Answer 2

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

Stirring

best answer for Java 8+ – Phytography

Cool, didn't know about that one. Java 8 definitively fixed a few PITA's. – Eben

Good way. But unfortunately doesn't work with float or double arguments. Mod binary operator (%) also works with float and double operands. – Tacitus

In some ways the better question is how to do 'xyz' math operation in Java. What complicates this is people's belief that there is one correct way to do it. – Rosado

Answer 3

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.

Priestly

Answer 4

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.

Guacharo

In number theory it's not always positive... They fall into congruence classes. You are free to choose whatever candidate from that class for your notation purposes, but the idea is that it maps to all of that class, and if using a specific other candidate from it makes a certain problem significantly simpler (choosing -1 instead of n-1 for example) then have at it. – Angular

Definitely the case of a primadonna programmer who thinks he knows better than everyone else and just causes confusion for everyone. Should have used a different operator than % for remainder which has traditionally returned values between 0 and the modulo. This is likely to cause hard-to-find bugs and things like planes turning upside down when crossing the equator. Note that I'm not suggesting it be changed now. – Cockoftherock

@Richard Thomas: Agreed. About plane turning upside down : using quaternions avoid all this and makes the code much cleaner ( conceptually and programmatically). – Bleachers

Answer 5

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.

Fultz

That seems to assume that int is 32 bits. Which is probably mostly safe but the Java site says "int: By default, the int data type is a 32-bit signed two's complement integer,". That "by default" sounds a bit unsolid. [Edit: Digging further, it looks like the spec shows a solid 32 bits so carry on] – Cockoftherock

Answer 6

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.)

Trover

But the modulo operation requires a division which could be even slower (especially if the processor guesses the branch correctly almost all the time). So this is possibly better. – Corcyra

@KarstenR. You are right! I fixed the formula, now it works fine (but needs two more subtractions). – Trover

That is true @Corcyra – Trover

Answer 7

The floorMod method is the best way to go.

I am surprised no one posted the obvious.

Math.abs(a) % b

Breath

This is wrong, though. Taking the absolute value first changes modulus: floorMod(-1, 4) ==> 3 but Math.abs(-1) % 4 ==> 1. – Bissextile