33
\$\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\$
6
  • 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
21
\$\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\$
7
  • \$\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
6
\$\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\$
2
  • \$\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\$ 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
5
\$\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\$
0
4
\$\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\$
6
  • 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\$ 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
3
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Actually, if the arguments have different sign, no check is needed, so we possibly get a faster path there. \$\endgroup\$ Jul 6 '21 at 15:36
  • \$\begingroup\$ Re-ordering addition for the example you show is not prohibitively difficult. At every step, if we can find value of opposite sign to the running total, add that value next. Otherwise add and check the same-sign values available. Some impact on speed, though that could be mitigated with a bit of thought. \$\endgroup\$ Jul 6 '21 at 15:42
  • \$\begingroup\$ If the arguments have different signs, the result will be indeed be valid and no check needs to be done afterwards. But the only way to know if that's the case is to check for different signs at the start, which defeats the purpose of micro-optimization (since the scenario of equals signs still needs to be checked afterwards in the other case). \$\endgroup\$
    – Koen AIS
    Jul 6 '21 at 15:43
  • \$\begingroup\$ I agree that the reordering is easy, but it's still O(number of arguments). I'm guessing that that's not within the scope of the unstated requirements (i.e. that CanAdd should be as fast as possible). \$\endgroup\$
    – Koen AIS
    Jul 6 '21 at 15:49
  • 1
    \$\begingroup\$ Still should probably become a chat, but FYI here's the simultaneous check : (a ^ c) & (b ^ c) < 0, where a and b are the arguments and c is the result. \$\endgroup\$
    – Koen AIS
    Jul 6 '21 at 15:53
2
\$\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\$
3
  • \$\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.