How can I check if multiplying two numbers in Java will cause an overflow?

Question

I want to handle the special case where multiplying two numbers together causes an overflow. The code looks something like this:

int a = 20;
long b = 30;

// if a or b are big enough, this result will silently overflow
long c = a * b;

That's a simplified version. In the real program a and b are sourced elsewhere at runtime. What I want to achieve is something like this:

long c;
if (a * b will overflow) {
    c = Long.MAX_VALUE;
} else {
    c = a * b;
}

How do you suggest I best code this?

Update: a and b are always non-negative in my scenario.

It's too bad that Java doesn't provide indirect access to the CPU's [overflow flag](http://en.wikipedia.org/wiki/Overflow_flag), as [is done in C#](http://msdn.microsoft.com/en-us/library/khy08726.aspx). — Drew Noakes, Aug 20 '12 at 20:29

score 112 · Accepted Answer · answered Sep 24 '14 at 12:13

112

Java 8 has Math.multiplyExact, Math.addExact etc. for ints and long. These throw an unchecked ArithmeticException on overflow.

answered Sep 24 '14 at 12:13

bcoughlan

25,987
18
90
141

John Kugelman · Answer 2 · 2013-07-16T15:14:17.430

63

If a and b are both positive then you can use:

if (a != 0 && b > Long.MAX_VALUE / a) {
    // Overflow
}

If you need to deal with both positive and negative numbers then it's more complicated:

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if (a != 0 && (b > 0 && b > maximum / a ||
               b < 0 && b < maximum / a))
{
    // Overflow
}

Here's a little table I whipped up to check this, pretending that overflow happens at -10 or +10:

a =  5   b =  2     2 >  10 /  5
a =  2   b =  5     5 >  10 /  2
a = -5   b =  2     2 > -10 / -5
a = -2   b =  5     5 > -10 / -2
a =  5   b = -2    -2 < -10 /  5
a =  2   b = -5    -5 < -10 /  2
a = -5   b = -2    -2 <  10 / -5
a = -2   b = -5    -5 <  10 / -2

edited Jul 16 '13 at 15:14

answered Nov 01 '09 at 18:16

John Kugelman

349,597
67
533
578

I should mention that a and b are always non-negative in my scenario, which would simplify this approach somewhat. – Steve McLeod Nov 01 '09 at 18:17
3

I think this may fail a case: a = -1 and b = 10. The maximum / a expression result in Integer.MIN_VALUE and detects overflow when none existed – Kyle Dec 28 '14 at 02:34
This is really nice. For those wondering, the reason this works is that for integer `n`, `n > x` is the same as `n > floor(x)`. For positive integers division does an implicit floor. (For negative numbers it rounds up instead) – Thomas Ahle May 05 '15 at 22:44
To address the `a = -1` and `b = 10` issue, see my answer below. – Jim Pivarski Nov 03 '15 at 18:27

score 18 · Answer 3 · edited Feb 14 '18 at 11:47

18

There are Java libraries that provide safe arithmetic operations, which check long overflow/underflow. For example, Guava's LongMath.checkedMultiply(long a, long b) returns the product of a and b, provided it does not overflow, and throws ArithmeticException if a * b overflows in signed long arithmetic.

edited Feb 14 '18 at 11:47

Iulian Popescu

2,595
4
23
31

answered Dec 05 '12 at 03:16

reprogrammer

14,298
16
57
93

5

This is the best answer -- use a library which was implemented by people who really understand machine arithmetic in Java and which has been tested by lots of people. Don't attempt to write your own or use any of the half-baked untested code posted in the other answers! – Rich Jan 21 '14 at 11:22
@Enerccio -- I don't understand your comment. Are you saying that Guava won't work on all systems? I can assure you that it will work everywhere that Java does. Are you saying that reusing code is a bad idea in general? I disagree if so. – Rich Aug 10 '15 at 09:49
3

@Rich I am saying including huge library so you can use one function is a bad idea. – Enerccio Aug 10 '15 at 11:52
Why? If you're writing a large application, for example for a business, then an extra JAR on the classpath won't do any harm and Guava has lots of very useful code in it. It's much better to reuse their carefully tested code than to try to write your own version of the same (which I presume is what you recommend?). If you're writing in an environment where an extra JAR is going to be very expensive (where? embedded Java?) then perhaps you should extract just this class from Guava. Is copying an untested answer from StackOverflow better than copying Guava's carefully tested code? – Rich Aug 10 '15 at 12:48
Isn't throwing an exception a bit overkill for something a conditional if-then can handle? – victtim Jan 19 '18 at 14:30
Perhaps "SaturatedMultiply" is better if you want to avoid exceptions. http://google.github.io/guava/releases/snapshot/api/docs/src-html/com/google/common/math/LongMath.html#line.685 – victtim Jan 19 '18 at 14:42

Ulf Lindback · Answer 4 · 2009-11-01T18:19:39.430

6

You could use java.math.BigInteger instead and check the size of the result (haven't tested the code):

BigInteger bigC = BigInteger.valueOf(a) * multiply(BigInteger.valueOf(b));
if(bigC.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) {
  c = Long.MAX_VALUE;
} else {
  c = bigC.longValue()
}

edited Nov 01 '09 at 18:19

answered Nov 01 '09 at 18:07

Ulf Lindback

13,974
3
40
31

7

i find this solution rather slow – nothrow Nov 01 '09 at 18:14
It's probably the best way to do it, though. I assumed this was a numerical application, which is why I didn't recommend it offhand, but this really is probably the best way to solve this problem. – Stefan Kendall Nov 01 '09 at 18:15
2

I'm not sure you can use the '>' operator with BigInteger. the compareTo method should be used. – Pierre Nov 01 '09 at 18:16
changed to compareTo, and speed might matter or might not, depends on the circumstances where the code will be used. – Ulf Lindback Nov 01 '09 at 18:21

score 6 · Answer 5 · answered Aug 25 '17 at 02:33

6

Here is the simplest way I can think of

int a = 20;
long b = 30;
long c = a * b;

if(c / b == a) {
   // Everything fine.....no overflow
} else {
   // Overflow case, because in case of overflow "c/b" can't equal "a"
}

answered Aug 25 '17 at 02:33

Naren

2,706
1
21
15

score 4 · Answer 6 · edited Aug 30 '11 at 02:37

4

Use logarithms to check the size of the result.

edited Aug 30 '11 at 02:37

answered Nov 01 '09 at 18:09

High Performance Mark

77,191
7
105
161

do you mean: `ceil(log(a)) + ceil(log(b)) > log(Long.MAX)`? – Thomas Jung Nov 01 '09 at 18:16
1

I checked it. For small values it is 20% faster than BigInteger and for values near MAX it is nearly the same (5% faster). Yossarian's code is the fastest (95% & 75% faster than BigInteger). – Thomas Jung Nov 01 '09 at 19:09
I rather suspect that it may fail in some cases. – Tom Hawtin - tackline Nov 01 '09 at 23:47
Remember an integer log is effectively just counting the number of leading zeroes, and you can optimise some common cases (e.g. if ((a | b) & 0xffffffff00000000L) == 0) you know you're safe). On the other hand, unless you can get your optimisation down to 30/40-ish clock cycles for the commonest cases, John Kugelman's method will probably perform better (an integer division is c. 2 bits/clock cycle as I recall). – Neil Coffey Nov 02 '09 at 04:26
P.S. Sorr, I think I need an extra bit set in the AND mask (0xffffffff80000000L)-- it's a bit late, but you get the idea... – Neil Coffey Nov 02 '09 at 04:27
Oh, if you want it fast, take logs, add, and, if the answer is in range, take antilogs -- you've already computed the result Mark – High Performance Mark Nov 02 '09 at 12:20
`Long.numberOfTrailingZeros(a) + Long.numberOfTrailingZeros(b)` should be fast, but not always enough to determine – 4esn0k Nov 03 '15 at 16:33

score 4 · Answer 7 · edited Nov 02 '09 at 11:38

4

Does Java has something like int.MaxValue? If yes, then try

if (b != 0 && Math.abs(a) > Math.abs(Long.MAX_VALUE / b))
{
 // it will overflow
}

edit: seen Long.MAX_VALUE in question

edited Nov 02 '09 at 11:38

Steve McLeod

51,737
47
128
184

answered Nov 01 '09 at 18:12

nothrow

15,882
9
57
104

I didn't downvote but `Math.Abs(a)` doesn't work if `a` is `Long.MIN_VALUE`. – John Kugelman Nov 01 '09 at 18:31
@John - a and b are > 0. I think Yossarian's approach (b != 0 && a > Long.MAX_VALUE / b) is the best. – Thomas Jung Nov 01 '09 at 18:44
@Thomas, a and b are >= 0, that is, non-negative. – Steve McLeod Nov 01 '09 at 18:50
2

Right, but in that case no need for the Abs's. If negative numbers are allowed then this fails for at least one edge case. That's all I'm saying, just being nitpicky. – John Kugelman Nov 01 '09 at 18:59
in Java you must use Math.abs, not Math.Abs (C# guy?) – dfa Nov 01 '09 at 22:07
if a==1, and b==Long.MIN_VALUE, then this method overflows, but actually it doesn't. – Brian Jan 01 '14 at 08:30

score 4 · Answer 8 · answered Nov 03 '15 at 18:26

I'd like to build on John Kugelman's answer without replacing it by editing it directly. It works for his test case (MIN_VALUE = -10, MAX_VALUE = 10) because of the symmetry of MIN_VALUE == -MAX_VALUE, which isn't the case for two's complement integers. In actuality, MIN_VALUE == -MAX_VALUE - 1.

scala> (java.lang.Integer.MIN_VALUE, java.lang.Integer.MAX_VALUE)
res0: (Int, Int) = (-2147483648,2147483647)

scala> (java.lang.Long.MIN_VALUE, java.lang.Long.MAX_VALUE)
res1: (Long, Long) = (-9223372036854775808,9223372036854775807)

When applied to the true MIN_VALUE and MAX_VALUE, John Kugelman's answer yields an overflow case when a == -1 and b == anything else (point first raised by Kyle). Here's a way to fix it:

long maximum = Long.signum(a) == Long.signum(b) ? Long.MAX_VALUE : Long.MIN_VALUE;

if ((a == -1 && b == Long.MIN_VALUE) ||
    (a != -1 && a != 0 && ((b > 0 && b > maximum / a) ||
                           (b < 0 && b < maximum / a))))
{
    // Overflow
}

It's not a general solution for any MIN_VALUE and MAX_VALUE, but it is general for Java's Long and Integer and any value of a and b.

I just thought it would unnecessarily complicate it, since this solution only works if `MIN_VALUE = -MAX_VALUE - 1`, not any other case (including your example test case). I'd have to change a lot. — Jim Pivarski, Nov 03 '15 at 21:15
For reasons beyond the needs of the original poster; for people like me who found this page because they needed a solution for a more general case (handling negative numbers and not strictly Java 8). In fact, since this solution doesn't involve any functions beyond pure arithmetic and logic, it could be used for C or other languages as well. — Jim Pivarski, Nov 06 '15 at 04:19

StFS · Answer 9 · 2019-10-07T12:43:00.157

As has been pointed out, Java 8 has Math.xxxExact methods that throw exceptions on overflow.

If you are not using Java 8 for your project, you can still "borrow" their implementations which are pretty compact.

Here are some links to these implementations in the JDK source code repository, no guarantee whether these will stay valid but in any case you should be able to download the JDK source and see how they do their magic inside the java.lang.Math class.

Math.multiplyExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l925

Math.addExact(long, long) http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/lang/Math.java#l830

etc, etc.

UPDATED: switched out invalid links to 3rd party website to links to the Mercurial repositories of Open JDK.

rogerdpack · Answer 10 · 2013-07-16T18:37:25.947

3

Stolen from jruby

    long result = a * b;
    if (a != 0 && result / a != b) {
       // overflow
    }

UPDATE: This code is short and works well; however, it fails for a = -1, b = Long.MIN_VALUE.

One possible enhancement:

long result = a * b;
if( (Math.signum(a) * Math.signum(b) != Math.signum(result)) || 
    (a != 0L && result / a != b)) {
    // overflow
}

Note that this will catch some overflows without any division.

edited Jul 16 '13 at 18:37

answered Jun 01 '11 at 00:38

rogerdpack

62,887
36
269
388

You can use Long.signum instead of Math.signum – aditsu quit because SE is EVIL Apr 06 '14 at 05:36

score 2 · Answer 11 · edited Aug 30 '11 at 02:37

2

I am not sure why nobody is looking at solution like:

if (Long.MAX_VALUE/a > b) {
     // overflows
}

Choose a to be larger of the two numbers.

edited Aug 30 '11 at 02:37

answered Nov 01 '09 at 18:58

fastcodejava

39,895
28
133
186

2

I don't think it matters if `a` is the larger or the smaller? – Thomas Ahle May 05 '15 at 22:46

Thomas Jung · Answer 12 · 2009-11-02T08:22:03.533

1

Maybe:

if(b!= 0 && a * b / b != a) //overflow

Not sure about this "solution".

Edit: Added b != 0.

Before you downvote: a * b / b won't be optimized. This would be compiler bug. I do still not see a case where the overflow bug can be masked.

edited Nov 02 '09 at 08:22

answered Nov 01 '09 at 18:04

Thomas Jung

32,428
9
84
114

Also fails when overflow causes a perfect loop. – Stefan Kendall Nov 01 '09 at 18:17
Do you have an example of what you meant? – Thomas Jung Nov 01 '09 at 18:29
Just wrote a little test: Using BigInteger is 6 times slower than using this division approach. So I assume additional checks for corner cases is worth it performance-wise. – mhaller Nov 01 '09 at 18:36
Don't know much about java compilers, but an expression like `a * b / b` is likely to be optimized to just `a` in many other contexts. – SingleNegationElimination Nov 01 '09 at 22:09
TokenMacGuy - it cannot be optimised like that if there is a danger of overflow. – Tom Hawtin - tackline Nov 01 '09 at 23:46
@StefanKendall Do you have an example of numbers that cause 'a perfect loop'? – Thomas Ahle May 05 '15 at 22:49

dfa · Answer 13 · 2009-11-02T08:48:57.003

1

maybe this will help you:

/**
 * @throws ArithmeticException on integer overflow
 */
static long multiply(long a, long b) {
    double c = (double) a * b;
    long d = a * b;

    if ((long) c != d) {
        throw new ArithmeticException("int overflow");
    } else {
        return d;
    }
}

edited Nov 02 '09 at 08:48

answered Nov 01 '09 at 21:47

dfa

114,442
31
189
228

Wont help as one of the operands is `long`. – Tom Hawtin - tackline Nov 01 '09 at 23:50
2

Did you even test this? For any large but not overflowing values of a & b this will fail due to rounding errors in the double version of the multiply (try e.g. 123456789123L and 74709314L). If you don't understand machine arithmetic, guessing an answer to this kind of precise question is worse than not answering, as it will mislead people. – Rich Jan 21 '14 at 11:13

score 1 · Answer 14 · answered Jan 15 '21 at 08:39

I don't answer, but looking at the Java's code, it is simple. In JDK8, It converts into long operation, and downcast the result to int value, and compares with long result to see if value has changed. Below code explains better than me.

@HotSpotIntrinsicCandidate
public static int multiplyExact(int x, int y) {
    long r = (long)x * (long)y;
    if ((int)r != r) {
        throw new ArithmeticException("integer overflow");
    }
    return (int)r;
}

xuan · Answer 15 · 2012-12-05T06:18:17.633

c / c ++ (long * long):

const int64_ w = (int64_) a * (int64_) b;    
if ((long) (w >> sizeof(long) * 8) != (long) w >> (sizeof(long) * 8 - 1))
    // overflow

java (int * int, sorry I didn't find int64 in java):

const long w = (long) a * (long) b;    
int bits = 32; // int is 32bits in java    
if ( (int) (w >> bits) ！= (int) (w >> (bits - 1))) {
   // overflow
}

1.save the result in large type (int*int put the result to long, long*long put to int64)

2.cmp result >> bits and result >> (bits - 1)

How can I check if multiplying two numbers in Java will cause an overflow?

15 Answers15

Linked

Related