133

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
CharlesB
  • 86,532
  • 28
  • 194
  • 218
fent
  • 17,861
  • 15
  • 87
  • 91
  • 14
    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. –  Dec 10 '10 at 18:46
  • 5
    this is just weird for me. i thought it should only return negative if b is negative. – fent Dec 10 '10 at 18:55
  • 1
    possible duplicate of [How does java do modulus calculations with negative numbers?](http://stackoverflow.com/questions/4403542/how-does-java-do-modulus-calculations-with-negative-numbers) – Erick Robertson Dec 10 '10 at 18:58
  • 2
    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. – fent Dec 10 '10 at 19:20
  • 7
    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. – Erick Robertson Dec 10 '10 at 19:23
  • 1
    Java doesn't have a modulus operator. The operator that many programmers mistakenly call modulus is actually called the [remainder operator](https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op1.html), which hints at why it behaves as it does. – StackOverthrow Oct 01 '18 at 19:55

7 Answers7

169

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

SuperStormer
  • 4,997
  • 5
  • 25
  • 35
Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • 3
    this works better thanks. and it works for negative numbers that are much larger than b too. – fent Dec 10 '10 at 18:55
  • this is a really good answer! as close to elegant as java will let you go, I think – mfsiega Oct 25 '12 at 00:20
  • @PeterLawrey - Thanks, I needed this solution too, but would you be willing to explain why it works? – Lou Apr 12 '14 at 10:28
  • 6
    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). – ethanfar Apr 13 '14 at 05:53
  • 2
    @eitanfar I've included your excellent explanation into the answer (with a minor correction for `a < 0`, maybe you could have a look) – Maarten Bodewes Sep 13 '14 at 10:46
  • 7
    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. – Thorbear Sep 16 '15 at 09:47
  • 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) – Mikepote Mar 08 '16 at 09:45
  • 2
    @Mikepote using a `while` would be slower if you really need it except you only need an `if` in which case it is actually faster. – Peter Lawrey Mar 08 '16 at 09:59
  • @PeterLawrey I have a question [here](http://stackoverflow.com/questions/36705814/swap-functions-of-collections-class-fails-on-negative-value) in which `hashCode` method of String is returning negative value bcoz of which my index value is coming as negative. I wanted to see if you can help out. – arsenal Apr 19 '16 at 00:45
  • 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`. – Rômulo Ceccon Mar 17 '17 at 13:18
  • 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. – runcoderun Oct 17 '18 at 17:30
  • 1
    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. https://stackoverflow.com/questions/40692016/javascript-modulo-operator-behaves-differently-from-other-languages – Chris Golledge Apr 09 '21 at 21:02
127

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
John Krueger
  • 1,436
  • 1
  • 10
  • 4
16

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.

Ibrahim Arief
  • 8,742
  • 6
  • 34
  • 54
10

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.

Chris Golledge
  • 350
  • 4
  • 7
  • 1
    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. – BeUndead Jul 10 '19 at 14:11
  • 1
    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. – Richard Thomas Nov 10 '20 at 05:27
  • @Richard Thomas: Agreed. About plane turning upside down : using quaternions avoid all this and makes the code much cleaner ( conceptually and programmatically). – Jérôme JEAN-CHARLES May 19 '22 at 11:53
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.

Scott Carey
  • 1,587
  • 17
  • 13
  • 3
    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] – Richard Thomas Nov 10 '20 at 05:33
2

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

Stefan Reich
  • 1,000
  • 9
  • 12
0

The floorMod method is the best way to go.

I am surprised no one posted the obvious.

Math.abs(a) % b
John Glen
  • 771
  • 7
  • 24
  • 1
    This is wrong, though. Taking the absolute value first changes modulus: `floorMod(-1, 4) ==> 3` but `Math.abs(-1) % 4 ==> 1`. – just-max Jun 30 '23 at 11:49