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

StackOverflow https://stackoverflow.com/questions/1657834

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.

Was it helpful?

Solution

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

OTHER TIPS

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

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.

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

Use logarithms to check the size of the result.

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

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.

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"
}

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.

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.

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.

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;
    }
}

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 on a 3rd party website, no guarantee whether these will stay valid but in any case you should be able to go into the JDK source and see how they do their magic inside the java.lang.Math class.

Math.multiplyExact(long, long) http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/Math.java?av=f#882

Math.addExact http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/lang/Math.java?av=f#805

etc, etc.

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)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top