30
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Have you done any profiling which showed that this method is a bottleneck in your application? \$\endgroup\$ – palacsint Nov 24 '11 at 19:08
  • 1
    \$\begingroup\$ @palacsint no this isn't a bottleneck in my application.. just that I'm interested in algorithms related to range checking and was wondering if there's a better solution (besides the casting one) =) \$\endgroup\$ – Pacerier Nov 24 '11 at 20:30
  • \$\begingroup\$ I have seen some (usually C/C++) questions and answers on SO with nice bitwise code, maybe you want to check them :-) \$\endgroup\$ – palacsint Nov 24 '11 at 22:18
  • \$\begingroup\$ I don't know your ultimate purpose, but depending on what you are trying to accomplish, perhaps, you might find Guava's checked arithmetic useful. Note this is not actually a direct response to your query. code.google.com/p/guava-libraries/wiki/MathExplained \$\endgroup\$ – DPM Jan 28 '12 at 23:56
  • \$\begingroup\$ Speaking of checked arithmetic - Java8+ now has that in its Math class (you can see my other answer here about Java8+). \$\endgroup\$ – cellepo Nov 19 '18 at 3:14
20
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ This Answer is valid, but fwiw, other Answer by Todd Lehman seems to be even less lines of code. But this is still a good Answer :) \$\endgroup\$ – cellepo Nov 11 '18 at 20:30
  • 1
    \$\begingroup\$ Thank you for including the illuminating examples of how Apache & Guava also use long-conversion. I think its helpful to not that they accept exactly 2 int params, which I think precludes any possibility of long-overflow - attempting to sum more than 2 params starts down the path pf possibly reaching long-overflow... However I believe Answers like this implicitly account for long-overflow, by them having an "early out" loop/method exit of the Integer-size check (within each loop iteration). \$\endgroup\$ – cellepo Nov 13 '18 at 21:56
  • 1
    \$\begingroup\$ @cellepo: Thanks! Yeah, an explicit values.length check would help reasoning here. Just for fun, you need an array with at least (Long.MAX_VALUE / Integer.MAX_VALUE) = (2^63−1) / (2^31−1) = 4294967298 int elements to overflow the long sum variable. This 4294967298 is the double of the possible maximal array length in Java :-) \$\endgroup\$ – palacsint Nov 14 '18 at 1:18
  • \$\begingroup\$ @ palacsint ah good point with that math analysis (thanks!) - I think it infers that the long-overflow I mentioned is actually not possible, because even an array of max size completely-filled with MAX_VALUE instances would not be enough to long-overflow the sum. \$\endgroup\$ – cellepo Nov 19 '18 at 3:02
  • 1
    \$\begingroup\$ So maybe I was getting too theoretical :) At least for arrays on a JVM - I think long-overflow could still happen with a Collection that can hold sufficiently-more (if such a Collection exists), a custom Object (like a manual/custom linked list data structure), or in math analysis involving max-sizes for number types. But again, getting a bit theoretical (especially with the last Math analysis I just mentioned) ... :) \$\endgroup\$ – cellepo Nov 19 '18 at 3:09
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It might be more readable (and exactly equivalent in speed) to have the try/catch outside the loop. I.e. try { for (int curArg: args) me = Math.addExact(me, curArg); return true; } catch(ArithmeticException ae) { return false; } \$\endgroup\$ – Toby Speight Nov 12 '18 at 18:33
  • \$\begingroup\$ Yes that's a valid alternative. I personally like mine better, as I prefer a try block to be as close/limited to the actual line(s)/call(s) that could be the source of Exception - rather than the try encompassing the loop/guard itself also, where the loop/guard would never throw the Exception. Limiting the try block as I prefer, to me, is more readable as the limiting makes it more clear/specific where the Exception source could be (helps de-bugging too). Toby Speight alternative is also valid & I'm not criticizing it (just clarifying my personal preference in the context of alternative). \$\endgroup\$ – cellepo Nov 13 '18 at 20:26
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ +1 for the mention of long conversion. \$\endgroup\$ – cellepo Nov 12 '18 at 2:23
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ It is possible that longSum could ALSO overflow (at least eventually, when therefore after intSum had to also overflow prior). However, I'm not sure if it is possible (in a case of both overflowing) if it could end up that intSum == longSum ends up returning a false positive (of true)? In other words, could intSum overflow & longSum overflow values (within the same canAdd call) ever end up being equal (therefore invalidly returning true)? \$\endgroup\$ – cellepo Nov 13 '18 at 21:22
  • 1
    \$\begingroup\$ If my above comment is accurate about the false-positive possibility, then I think that is then an [invalidating] consequence of there being no "early out" as mentioned in this Answer. (Some other Answers here do have an "early out" btw). \$\endgroup\$ – cellepo Nov 13 '18 at 22:09
  • 1
    \$\begingroup\$ fwiw, my comments on this Answer are not intended as personal criticism, but rather as constructive critique (and I might be wrong about my skepticism). This was otherwise my favorite Answer a few days prior [when I upvoted this!], and led me to my other Answer here (containing "food-for-thought") - however if my skepticism is correct, then that other Answer of mine also suffers from the same long-overflow without "early out" (and is noted there as such). Regardless of if my skepticism is correct, I still appreciate this Answer for its other illuminating qualities :) \$\endgroup\$ – cellepo Nov 13 '18 at 22:18
  • 1
    \$\begingroup\$ @cellepo — Thanks! Your skepticism is correct! If the length of the list is in the billions (2^32 or more, I believe) then some combination of input could provide false positives if the 31-bit positive int values sum to a value large enough to exceed the 63-bit positive value of a long. I've added a second version that avoids this shortcoming by exiting immediately upon detecting any int overflow. \$\endgroup\$ – Todd Lehman Nov 14 '18 at 18:33
  • 1
    \$\begingroup\$ Yep, 2nd version's simple check would account for long-overflow! However maybe I should apologize for getting too theoretical: I think I recently realized, with insight from @ palacsint on comments in their Answer, that an array's max-capacity would actually preclude ever reaching long-overflow (at least on a JVM) - see comment discussion on that other Answer for more details. (Sorry if this ended up being a trivial rabbit hole). \$\endgroup\$ – cellepo Nov 19 '18 at 3:24
1
\$\begingroup\$

[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;
}
\$\endgroup\$
  • \$\begingroup\$ If Java 8, you should see my other Answer on this page. \$\endgroup\$ – cellepo Nov 12 '18 at 2:38
  • \$\begingroup\$ If not Java8+, and you want/need to account for long-overflow, improving this Answer as such would essentially arrive at other Answers here that use an "early out" loop/method exit of an Integer-size check (within each loop iteration) - so use one of those Answers :) \$\endgroup\$ – cellepo Nov 13 '18 at 22:03
  • \$\begingroup\$ fwiw - if args were int (instead of long), the long-overflow possibility would then be precluded (on a JVM at least, due to max-capacity of an array) - see comments on other Answer here by @ palacsint for more discussion. \$\endgroup\$ – cellepo Nov 19 '18 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.