CODEWITHSUNDEEP
javamathlong-integerinteger-overflow
Steve McLeod
Steve McLeod

Reputation: 52468

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

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.

Upvotes: 118

Views: 43573

Answers (15)

Mohan Narayanaswamy
Mohan Narayanaswamy

Reputation: 2149

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

Upvotes: 1

StFS
StFS

Reputation: 1722

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.

Upvotes: 3

reprogrammer
reprogrammer

Reputation: 14728

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.

Upvotes: 18

Naren
Naren

Reputation: 2726

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

Upvotes: 6

Jim Pivarski
Jim Pivarski

Reputation: 5974

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.

Upvotes: 4

bcoughlan
bcoughlan

Reputation: 26627

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

Upvotes: 115

rogerdpack
rogerdpack

Reputation: 66851

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.

Upvotes: 3

John Kugelman
John Kugelman

Reputation: 361917

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

Upvotes: 67

xuan
xuan

Reputation: 21

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)

Upvotes: -1

fastcodejava
fastcodejava

Reputation: 41117

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.

Upvotes: 2

High Performance Mark
High Performance Mark

Reputation: 78364

Use logarithms to check the size of the result.

Upvotes: 4

nothrow
nothrow

Reputation: 16178

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

Upvotes: 4

dfa
dfa

Reputation: 116382

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

Upvotes: 1

Thomas Jung
Thomas Jung

Reputation: 33092

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.

Upvotes: 1

Ulf Lindback
Ulf Lindback

Reputation: 14190

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

Upvotes: 7

Related Questions