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.

Solution 1

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

Solution 2

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

Solution 3

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.

Solution 4

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()
}

Solution 5

Use logarithms to check the size of the result.

View more solutions

Comments

[Drew Noakes]

It's too bad that Java doesn't provide indirect access to the CPU's overflow flag, as is done in C#.

[nothrow]

i find this solution rather slow

[Stefan Kendall]

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.

[Thomas Jung]

do you mean: ceil(log(a)) + ceil(log(b)) > log(Long.MAX)?

[LabRat01010]

I'm not sure you can use the '>' operator with BigInteger. the compareTo method should be used.

[Stefan Kendall]

Also fails when overflow causes a perfect loop.

[Steve McLeod]

I should mention that a and b are always non-negative in my scenario, which would simplify this approach somewhat.

[Ulf Lindback]

changed to compareTo, and speed might matter or might not, depends on the circumstances where the code will be used.

[Thomas Jung]

Do you have an example of what you meant?

[John Kugelman]

I didn't downvote but Math.Abs(a) doesn't work if a is Long.MIN_VALUE.

[mhaller]

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.

[Thomas Jung]

@John - a and b are > 0. I think Yossarian's approach (b != 0 && a > Long.MAX_VALUE / b) is the best.

[Steve McLeod]

@Thomas, a and b are >= 0, that is, non-negative.

[John Kugelman]

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.

[Thomas Jung]

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

[dfa]

in Java you must use Math.abs, not Math.Abs (C# guy?)

[SingleNegationElimination]

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.

[Brett]

TokenMacGuy - it cannot be optimised like that if there is a danger of overflow.

[Brett]

I rather suspect that it may fail in some cases.

[Brett]

Wont help as one of the operands is long.

[Neil Coffey]

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]

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

[High Performance Mark]

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

[Brian]

if a==1, and b==Long.MIN_VALUE, then this method overflows, but actually it doesn't.

[Rich]

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]

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!

[aditsu quit because SE is EVIL]

You can use Long.signum instead of Math.signum

[Kyle]

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

[Thomas Ahle]

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]

I don't think it matters if a is the larger or the smaller?

[Thomas Ahle]

@StefanKendall Do you have an example of numbers that cause 'a perfect loop'?

[Rich]

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

[Enerccio]

@Rich I am saying including huge library so you can use one function is a bad idea.

[Rich]

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?

[4esn0k]

Long.numberOfTrailingZeros(a) + Long.numberOfTrailingZeros(b) should be fast, but not always enough to determine

[Jim Pivarski]

To address the a = -1 and b = 10 issue, see my answer below.

[Jim Pivarski]

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]

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.

[victtim]

Isn't throwing an exception a bit overkill for something a conditional if-then can handle?

[victtim]

Perhaps "SaturatedMultiply" is better if you want to avoid exceptions. google.github.io/guava/releases/snapshot/api/docs/src-html/c‌​om/…