9

If I have an assignment

Long c = a + b;

Is there an easy way to check that a + b is not bigger/smaller than Long.MAX_VALUE/Long.MIN_VALUE?

Kaur Kase
  • 126
  • 1
  • 7

4 Answers4

17

Using Guava, it's as simple as

long c = LongMath.checkedAdd(a, b); // throws an ArithmeticException on overflow

which is, I'd like to think, very readable indeed. (LongMath Javadoc here.)

For the sake of fairness, I'll mention that Apache Commons provides ArithmeticUtils.addAndCheck(long, long).

If you want to know how they work, well, the answer is one line of bit-hackery for Guava: the result doesn't overflow if (a ^ b) < 0 | (a ^ (a + b)) >= 0. This is based on the trick that the bitwise XOR of two numbers is nonnegative iff they have the same sign.

So (a ^ b) < 0 is true if a and b have different signs, and if that's the case it'll never overflow. Or, if (a ^ (a + b)) >= 0, then a + b has the same sign as a, so it didn't overflow and become negative.

(For more tricks like this, investigate the lovely book Hacker's Delight.)

Apache uses more complicated casework based on the sign of a and b.

Iulian Popescu
  • 2,595
  • 4
  • 23
  • 31
Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • +1 for guava. Even if comparison (as originally suggested by me) can possibly work (although I'm too sleepy to think it properly), prefer the ready-to-use function – Bozho Jan 29 '12 at 22:28
  • Full disclosure: I'm the author of `LongMath` and the rest of Guava's common.math package...but @Bozho is correct that it's generally better to rely on library code rather than rolling your own implementation. (In particular, this code has already been tested *very* exhaustively, so you don't have to!) – Louis Wasserman Jan 29 '12 at 22:32
  • Very cool. Adding another entire library may be overkill for such a simple case (detecting overflow in this case is trivial), but if you're *already* using Guava... – T.J. Crowder Jan 29 '12 at 22:34
  • Indeed. And I might mention that `com.google.common.math` has many goodies beyond overflow-checked arithmetic. ;) Also, not every overflow check is this trivial -- in particular, checking for overflow when multiplying longs is significantly harder: http://docs.guava-libraries.googlecode.com/git-history/release/javadoc/src-html/com/google/common/math/LongMath.html#line.458 – Louis Wasserman Jan 29 '12 at 22:35
  • It might not be the best for an assignment, but it is certainly interesting to have a look at the library. – Maarten Bodewes Jan 29 '12 at 22:45
  • Agreed. (In all honesty, I genuinely missed the homework tag on the question, which does make the use of outside libraries less appropriate.) – Louis Wasserman Jan 29 '12 at 22:48
  • Is there any reason why `a+b < a` isn't good enough to check for overflow? Obviously if we also want to check for underflows we need the usual trickery, but if not that should be fine. If there's an overflow we compute `a + b - 2^32` after all which is guaranteed to be always negative (and there can't be any overflow if a or b are negative). – Voo Jan 29 '12 at 22:52
  • @Louis After reading my first post I deleted it and restated it, sorry for the confusion. I hope that makes it clearer! – Voo Jan 29 '12 at 22:53
  • The homework tag actually got there by accident. Thanks for the thorough explanation on the workings of it and the library suggestion. Hard to choose which answer to accept, both are very good :) – Kaur Kase Jan 29 '12 at 22:54
  • @Voo: Overflow, underflow, both are evil and bad and more or less equivalent. I just use the term "overflow" for both cases. – Louis Wasserman Jan 29 '12 at 22:56
  • 1
    @KaurKase: As a general rule, when dealing with finicky math stuff -- which overflow certainly is -- I strongly recommend using library solutions that have already been tested for you. (Even if it's not a library I wrote, heh.) There are just so many ways to screw these things up, as I found out while writing the library... – Louis Wasserman Jan 29 '12 at 22:58
13

It's only an issue if they have the same sign (and are both !0), since otherwise you're safe from overflow. If overflow occurs, the sign of the result will flip. So:

long r = a + b;
if ( (a < 0 && b < 0 && r >= 0) ||
     (a > 0 && b > 0 && r <= 0) ) {
    // Overflow occurred
}
T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • 2
    Voted up, easiest, most readable and best way. Hopefully the course won't go for a more 'optimized' mathematical method. – Maarten Bodewes Jan 29 '12 at 22:38
  • @owlstead, if the compiler is smart enough it can use the CPU "carry" flag, so the solution is good enough. back in the day the only arithmetic was done via the carry. – bestsss Jan 29 '12 at 22:42
  • Even though we now know that it isn't homework, keep my upvote for an easy-to-understand solution. – Louis Wasserman Jan 30 '12 at 01:43
0

One option would be to use the BigInteger class to do the exact computation, then check whether the result is greater than or smaller than the value in question. For example:

if (BigInteger.valueOf(a).add(BigInteger.valueOf(b)).compareTo(BigInteger.valueOf(Long.MAX_VALUE) > 1) {
    /* Overflow occurred. */
} else {
    /* No overflow occurred.
}

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • If you're going to go ahead and use the full power of `BigInteger`, you could just check `myBigInt.bitLength() < Long.SIZE`, I'm almost positive. – Louis Wasserman Jan 29 '12 at 22:26
  • @LouisWasserman correct because of the lesser than, otherwise it would be an off by one. I don't think either of the two options is readable though, and the one of the answer only takes in Long.MAX_VALUE, not Long.MIN_VALUE... – Maarten Bodewes Jan 29 '12 at 22:42
  • Agreed that this is less readable than it could be. For reference, though I'd say that the BigInteger approach is the most readable way to check for overflow on *multiplication*, if you're not willing to use a library. – Louis Wasserman Jan 29 '12 at 22:44
0

the simple route:

if(a/2+b/2+(a&b&1)>long.MAX_VALUE/2||a/2+b/2<long.MIN_VALUE/2)...

you just need to hope that it doesn't get optimized to (a+b)/2

ratchet freak
  • 47,288
  • 5
  • 68
  • 106
  • I don't believe that this works correctly. Take a = Long.MAX_VALUE and b = 1. Then there is clearly an overflow if you add the two values, but if you cut them in half, a/2 = Long.MAX_VALUE / 2 and b/2 = 0, so a/2 + b/2 <= Long.MAX_VALUE. – templatetypedef Jan 29 '12 at 22:38
  • @templatetypedef I fixed that tidbit (added the overflow) – ratchet freak Jan 29 '12 at 23:20