Int overflow check in Java

Question

I have a piece of code that takes a couple of integers and check if performing an addition on the inputs would result in an overflow.

I was wondering if this code is SOLID:

public static boolean CanAdd(int me, int... args) { 
    int total = me;
    for (int arg : args) {
        if (total >= 0) {
            if (java.lang.Integer.MAX_VALUE - total >= arg) { // since total is positive, (MaxValue - total) will never overflow
                total += arg;
            } else {
                return false;
            }
        } else {
            if (java.lang.Integer.MIN_VALUE- total <= arg) { // same logic as above
                total += arg;
            } else {
                return false;
            }
        }
    }
    return true;
}

Does anyone have a better (faster) way to achieve the same thing?

Answer 1

I haven't found any input which isn't handled well by your code. Here are some tests:

assertTrue(CanAdd(0, Integer.MAX_VALUE));
assertTrue(CanAdd(0, Integer.MIN_VALUE));
assertTrue(CanAdd(Integer.MIN_VALUE, 0));
assertTrue(CanAdd(-1, Integer.MAX_VALUE));
assertFalse(CanAdd(1, Integer.MAX_VALUE));
assertFalse(CanAdd(-1, Integer.MIN_VALUE));

So, it works but it isn't an easy task to read it. If this isn't a bottleneck in an application I would use a long:

public static boolean canAdd(int... values) {
    long sum = 0;
    for (final int value: values) {
        sum += value;
        if (sum > Integer.MAX_VALUE) {
            return false;
        }
        if (sum < Integer.MIN_VALUE) {
            return false;
        }
    }
    return true;
}

I think it's easier to read and maintain.

Finally, a note: according to Code Conventions for the Java Programming Language the name of your method should be canAdd (with lowercase first letter).

Methods should be verbs, in mixed case with the first letter lowercase, with the first letter of each internal word capitalized.

Edit:

Apache Commons Math also uses long conversion:

public static int addAndCheck(int x, int y)
        throws MathArithmeticException {
    long s = (long)x + (long)y;
    if (s < Integer.MIN_VALUE || s > Integer.MAX_VALUE) {
        throw new MathArithmeticException(LocalizedFormats.OVERFLOW_IN_ADDITION, x, y);
    }
    return (int)s;
} 

As well as Guava:

public static int checkedAdd(int a, int b) {
    long result = (long) a + b;
    checkNoOverflow(result == (int) result);
    return (int) result;
}

Answer 2

All other Answers here (as of this writing) are valid. But if you are Java 8+, you probably would want to be even more precise with Java 8+'s Math.addExact(int, int):

public static boolean canSumToInt(int me, int... args){
    for(int curArg: args){
        try{
            me = Math.addExact(me, curArg);
        }catch(ArithmeticException ae){
            return false;
        }
    }
    return true;
}

Overflow would throw ArithmeticException.

Answer 3

About the current code:

• I'd rename CanAdd to canAdd (according to the coding conventions).
• Rename me to value (it's more descriptive), and args to values and arg to currentValue.
• Remove the unnecessary java.lang package prefix.

public static boolean canAdd(int value, int... values) {
    int total = value;
    for (int currentValue: values) {
        if (total >= 0) {
            // since total is positive, (MaxValue - total) will never
            // overflow
            if (Integer.MAX_VALUE - total >= currentValue) {
                total += currentValue;
            } else {
                return false;
            }
        } else {
            // same logic as above
            if (Integer.MIN_VALUE - total <= currentValue) {
                total += currentValue;
            } else {
                return false;
            }
        }
    }
    return true;
}

I have also moved the comments a line up to avoid horizontal scrolling.

I don't really like the value and values here so I've changed the first two lines a little bit:

public static boolean canAdd(int... values) {
    int total = 0;
    ...
}

If you invert the inner if statements you could eliminate the else keywords:

if (total >= 0) {
    if (Integer.MAX_VALUE - total < currentValue) {
        return false;
    }
    total += currentValue;
} else {
    if (Integer.MIN_VALUE - total > currentValue) {
        return false;
    }
    total += currentValue;
}

The += is the same in both branches therefore it could be moved after the if:

if (total >= 0) {
    if (Integer.MAX_VALUE - total < currentValue) {
        return false;
    }
} else {
    if (Integer.MIN_VALUE - total > currentValue) {
        return false;
    }
}
total += currentValue;

Introducing a explanatory boolean variable could make it shorter and save an indentation level:

 public static boolean canAdd(int... values) {
    int total = 0;
    for (int currentValue: values) {
        final boolean positiveTotal = total >= 0;
        if (positiveTotal && (Integer.MAX_VALUE - total < currentValue)) {
            return false;
        }
        if (!positiveTotal && (Integer.MIN_VALUE - total > currentValue)) {
            return false;
        }
        total += currentValue;
    }
    return true;
}

But I think it's still hard to understand. I'd go with long conversion.

Answer 4

Your logic looks solid to me. It's subtle, though.

Here is another version using long, but with much simpler logic:

public static boolean canAdd(int... values) {
    long longSum = 0;
    int intSum = 0;
    for (final int value: values) {
        intSum += value;
        longSum += value;
    }
    return intSum == longSum;
}

That's the most straightforward way I can think to write it. Note that there is no "early out" in this loop, meaning it will always run to the end of the list. However, not having any conditionals, it's likely to be faster in many cases, if that matters.

(6 years later) Here is an updated version inspired by user 'cellepo' that stops as soon as it detects overflow, in order to avoid false positives (possible in the earlier version if the list of values was in the billions):

public static boolean canAdd(int... values) {
    long longSum = 0;
    int intSum = 0;
    for (final int value: values) {
        intSum += value;
        longSum += value;
        if (intSum != longSum)
            return false;
    }
    return true;
}

Answer 5

The code is correct from a realistic point of view but implements a stricter criterion than actually stated. Consider e.g.:

2147483647 + 2147483647 + (-2147483648) + (-2147483648)

Here, the result could be a "solid" -2 but CanAdd rejects it nevertheless. As such, the code does not satisfy its requirements (but, in this case, I'd almost certainly adjust the requirements instead of the code ;-).

On a more practical note: simply performing each addition (regardless of overflows), followed by a check if the sign of the result is as expected could marginally improve performance (it suffices to check that at least one argument has the same sign as that of the result, which can be done using trivial bit-wise operations - e.g. (a ^ c) & (b ^ c) >= 0, where a and b are the arguments and c is the result).

PS: if (and that's a big if) the code may not yield false negatives even in cases such as in the "-2" example, it'd be better to keep track of the difference d between the number of overflows (positive → negative) and the number of underflows (negative → positive), e.g. by if ((a ^ c) & (b ^ c) < 0) d += c < 0 ? -1 : 1;. CanAdd should then return d == 0.

Answer 6

[note: This is more of a "food-for-thought" Answer, since I ended up realizing it could actually be invalid when called with enough args to cause long-overflow... but I thought this might still be worth posting to show other possibilities with long...]

This is not asymptotically faster (still linear O(|args|) like in the Question), but is many less lines of body code (3), and is trivially faster due to only 1 logic/if-check:

public static boolean canSumToInt(long... args){
    long sum = 0;
    for(long curLong: args) sum += curLong;
    return Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE;
}

• Can even still call this with int-type args, because of numeric promotion of [smaller data type] int -> [larger data type] long (actual numeric value ends ups the same)
• I don't see why you would need a separate/additional/distinct me parameter - you can just make me the first value in args
• The technically possible invalidity I mentioned however, is that the loop-summing could reach a point where there is long-overflow (which would go "undetected") with sufficiently-large-magnitude individual args or sufficiently-many args - and that overflowed sum could end up being int-type-magnitude, which would return a false-positive [of true]

However you could even save 1 more line of code by re-introducing additional me parameter:

public static boolean canSumToInt(long me, long... args){
    for(long curLong: args) me += curLong;
    return Integer.MIN_VALUE <= me && me <= Integer.MAX_VALUE;
}