How to Check If Multiplying Two Numbers in Java Will Cause an Overflow

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

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

How to detect and prevent integer overflow when multiplying an integer by float in Java?

Below is a C approach that may shed light in Java.

Perform the multiplication using double, not float math before the assginment to gain the extra precision/range of double. Overflow is not then expected.

A compare like c > Integer.MAX_VALUE suffers from Integer.MAX_VALUE first being converted into a double. This may lose precision.^*1 Consider what happens if the converted value is Integer.MAX_VALUE + 1.0. Then if c is Integer.MAX_VALUE + 1.0, code will attempt to return (int) (Integer.MAX_VALUE + 1.0) - not good. Better to use well formed limits. (Negative ones too.) In C, maybe Java, floating point conversion to int truncates the fraction. Special care is needed near the edges.

#define INT_MAX_PLUS1_AS_DOUBLE ((INT_MAX/2 + 1)*2.0)

int mulInt(int a, float b) {
  // double c = a * b;
  double c = (double) a * b;
  
  //return c > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)c;
  if (c < INT_MAX_PLUS1_AS_DOUBLE && c - INT_MIN > -1.0) {
    return (int) c;
  } 
  if (c > 0) return INT_MAX;
  if (c < 0) return INT_MIN;
  return 0; // `b` was a NaN
}

c - INT_MIN > -1 is like c > INT_MIN - 1, but as INT_MIN is a -power-of-2, INT_MIN - 1 might not convert precisely to double. c - INT_MIN is expected to be exact near the edge cases.

---

^*1 When int is 32-bit (or less) and double is 64-bit (with 53-bit significand) not an issue. But important with wider integer types.

Overflow occurs with multiplication

I would use the m2 line instead of the m3 line.

Java evaluates the multiplication operator * from left to right, so 24 * 60 is evaluated first.

It just so happens that 24 * 60 * 60 * 1000 (one 1000) doesn't overflow, so that by the time you multiply by 1000L (the second 1000), the product is promoted to long before multiplying, so that overflow doesn't take place.

But as you mentioned in your comments, more factors can cause overflow in the int data type before multiplying the last long number, yielding an incorrect answer. It's better to use a long literal for the first (left-most) number as in m2 to avoid overflow from the start. Alternatively, you can cast the first literal as a long, e.g. (long) 24 * 60 * ....

Storing result of multiplication of two integers in long

Java has automatic widening from int to long, but that happens at assignment, but the multiplication of an int with another int produces an int, so you would get integer overflow first multiplying 32329 with 4746475, then the widening of the overflowed int result to long.

However, if you first cast at least one of the int to long, then the multiplication is done using long and the result is long, so no integer overflow.

Catch and compute overflow during multiplication of two large integers

1. Detecting the overflow:

x = a * b;
if (a != 0 && x / a != b) {
    // overflow handling
}

Edit: Fixed division by 0 (thanks Mark!)

2. Computing the carry is quite involved. One approach is to split both operands into half-words, then apply long multiplication to the half-words:

uint64_t hi(uint64_t x) {
    return x >> 32;
}

uint64_t lo(uint64_t x) {
    return ((1ULL << 32) - 1) & x;
}

void multiply(uint64_t a, uint64_t b) {
    // actually uint32_t would do, but the casting is annoying
    uint64_t s0, s1, s2, s3; 
    
    uint64_t x = lo(a) * lo(b);
    s0 = lo(x);
    
    x = hi(a) * lo(b) + hi(x);
    s1 = lo(x);
    s2 = hi(x);
    
    x = s1 + lo(a) * hi(b);
    s1 = lo(x);
    
    x = s2 + hi(a) * hi(b) + hi(x);
    s2 = lo(x);
    s3 = hi(x);
    
    uint64_t result = s1 << 32 | s0;
    uint64_t carry = s3 << 32 | s2;
}

To see that none of the partial sums themselves can overflow, we consider the worst case:

        x = s2 + hi(a) * hi(b) + hi(x)

Let B = 1 << 32. We then have

            x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
              <= B*B - 1
               < B*B

I believe this will work - at least it handles Sjlver's test case. Aside from that, it is untested (and might not even compile, as I don't have a C++ compiler at hand anymore).

How do you check if an arithmetic operation will overflow?

How is this done in C?

When wider math is available, code could use that.

int a,b;
...
int_twice_as_wide product = (int_twice_as_wide) a * b;
if (product < INT_MIN || product > INT_MAX) Handle_Overflow();

With signed integer math, overflow is undefined behavior (UB), so when wider math not readily available, code could perform various pre-tests for + - * / as done here.

For unsigned math, overflow "wraps around" ( a module UINT_MAX + 1). It is easy for + - (below). Division only need to watch for / 0.

unsigned a,b;
...
unsigned sum = a + b;
if (sum < a) Handle_Overflow();

The unsigned * is much like the above referenced signed * code with fewer tests.

bool is_undefined_umult1(unsigned a, unsigned b) {
  if (b > 0) {
    return a > UINT_MAX / b; 
  }
  return false;
}

---

it should return a u8 if it fits, otherwise a u16. But not a u16 in all cases.

C functions do not return different types depending upon value. Instead consider:

uint16_t unt8_mul(unt8_t a, unt8_t b) {
  return (uint16_t) a * b;
} 

For u8 * u8, avoid a * b as on 16-bit systems the multiplication is signed, the product may overflow and incur UB.

How to detect overflow of unsigned long multiplication in Java?

Edit
As promised in one of my comments to original post I will now post strict and correct solution. It has less divisions that Nathan's own formula (for those interested see last code line in his answer), but it has additional branching, so I am not sure it will be better performance-wise.

And, alas, it is not one-liner. Here it is:

    static boolean unsignedMultiplyOverflows(final long a, final long b) {
        if (a == 0 || b == 0) {
            return false;
        }

        // now proceed with non-zero input
        // we branch based upon parity of a and b
        final long aHalf = a >>> 1;
        final long bHalf = b >>> 1;
        final byte aLastBit = (byte) (a & 1);
        final byte bLastBit = (byte) (b & 1);
        if (aLastBit == 0) { // a = 2 * aHalf, meaning unsigned representation of a
            return Long.MAX_VALUE / b < aHalf;
        } else if (bLastBit == 0) { // b = 2 * bHalf
            return Long.MAX_VALUE / a < bHalf; // symmetrical to previous case
        } else { // a = 2 * aHalf + 1; b = 2 * bHalf + 1
            return (Long.MAX_VALUE - bHalf) / b < aHalf;
        }
    }

The formal proof is based on investigation of 2 cases, 1. At least one of multipliers is even, and 2. a,b both odd. I could add it if anyone is interested.

I have unit-tested it on full range of chars : 0 ~ 0xffff for overflow of 16-bit numbers, and also on some random long input, comparing results with both Nathan's method and BigInteger solution as a reference.

Hope that helps.

---

Related Topics