22

I have two numbers: A and B. I need to calculate A+B somewhere in my code. Both A and B are long long, and they can be positive or negative.

My code runs wrong, and I suspect the problem happens when calculating A+B. I simply want to check if A+B exceed long long range. So, any method is acceptable, as I only use it for debug.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
abcdabcd987
  • 2,043
  • 2
  • 23
  • 34
  • `if ((A<0 && B<0 && A+B>0) || (A>0 && B>0 && A+B<0)){/*Overflow*/}` You can only have overflow if both A and B have the same sign. If they do, and A+B doesn't have the same sign, then you have overflow issues. In other news, this is basically the fastest method around, since it executes in constant time, and only does the addition once. – FrankieTheKneeMan Apr 10 '13 at 08:28
  • 2
    You should post it as an answer. By the way, there's a corner case when `A=B=0x8000000000000000`, then `A+B=0` and your code doesn't work :p – riv Apr 10 '13 at 08:31
  • 1
    @FrankieTheKneeMan Integer overflow is undefined behaviour. – john Apr 10 '13 at 08:32
  • @John That's why I submitted it as a comment. My answer works on most compilers, and it's good enough for first step debug. – FrankieTheKneeMan Apr 10 '13 at 08:35
  • 1
    @AlexeyFrunze The alledged duplicate you mentioned deals with unsigned types, which behave in a well defined manner in all cases. Sigend integers do not behave in a well defined manner in some cases. – Oswald Apr 10 '13 at 08:37
  • @Oswald The "alleged duplicate" links to `IntSafe` and `SafeInt`, which contain functions for unsigned and signed types. – Alexey Frunze Apr 10 '13 at 09:02

4 Answers4

31

Overflow is possible only when both numbers have the same sign. If both are positive, then you have overflow if mathematically A + B > LLONG_MAX, or equivalently B > LLONG_MAX - A. Since the right hand side is non-negative, the latter condition already implies B > 0. The analogous argument shows that for the negative case, we also need not check the sign of B (thanks to Ben Voigt for pointing out that the sign check on B is unnecessary). Then you can check

if (A > 0) {
    return B > (LLONG_MAX - A);
}
if (A < 0) {
    return B < (LLONG_MIN - A);
}
return false;

to detect overflow. These computations cannot overflow due to the initial checks.

Checking the sign of the result of A + B would work with guaranteed wrap-around semantics of overflowing integer computations. But overflow of signed integers is undefined behaviour, and even on CPUs where wrap-around is the implemented behaviour, the compiler may assume that no undefined behaviour occurs and remove the overflow-check altogether when implemented thus. So the check suggested in the comments to the question is highly unreliable.

Community
  • 1
  • 1
Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
  • 4
    Not only checking the sign isn't guaranteed to work, but optimizers are using that absence of guarantee (for instance I just checked that gcc optimizes `a + 42 > a` to `true`). – AProgrammer Apr 10 '13 at 08:37
  • This would be much more readable if you wrapped it in a single expression, rather than throwing out `return` right and left. Something like `return a < 0 != b < 0 || (a < 0 ? b > LLONG_MIN - a : b < LLONG_MAX - a);`, for example. – James Kanze Apr 10 '13 at 08:45
  • 16
    @JamesKanze I find it more readable broken down into separate cases, but that's of course just my preference. – Daniel Fischer Apr 10 '13 at 08:51
  • @DanielFischer Hiding returns in `if` doesn't improve readability. As it appears here, my expression isn't particularly readable either, because I can't put newlines in it. Broken down over several lines, however, it would be much clearer. – James Kanze Apr 10 '13 at 09:12
  • 10
    FWIW, I agree with Daniel's style choice. I don't think that returns in an if are "hidden", especially not in a 7-line function. – Sebastian Redl Apr 10 '13 at 10:52
  • 1
    I also think it's clearer broken into several separate steps since it explicitly breaks out each case. Dogmatically jamming everything into a single statement due to religious hostility to multiple returns always being bad benefits no one; and replacing all the intermediate `return blah` lines with `retVal = blah` is just as bad. – Dan Is Fiddling By Firelight Apr 10 '13 at 13:07
  • `B > LLONG_MAX - A` implies `B > 0`, and the `B < 0` test is similarly useless. – Ben Voigt Feb 01 '15 at 17:57
7

Something like the following:

long long max = std::numeric_limits<long long>::max();
long long min = std::numeric_limits<long long>::min();

if(A < 0 && B < 0) 
    return B < min - A;
if(A > 0 && B > 0)
    return B > max - A;

return false;

We can reason about this as follows:

  • If A and B are opposite sign, they cannot overflow - the one greater than zero would need to be greater than max or the one less than zero would need to be less than min.

  • In the other cases, simple algebra suffices. A + B > max => B > max - A will overflow if they are both positive. Otherwise if they are both negative, A + B < min => B < min - A.

Yuushi
  • 25,132
  • 7
  • 63
  • 81
3

Also, if you're only using it for debug, you can use the following 'hack' to read the overflow bit from the last operation directly (assuming your compiler/cpu supports this):

int flags;
_asm {
    pushf       // push flag register on the stack
    pop flags   // read the value from the stack
}
if (flags & 0x0800) // bit 11 - overflow
    ...
riv
  • 6,846
  • 2
  • 34
  • 63
2

Mask the signs, cast to unsigned values, and perform the addition. If it's above 1 << (sizeof(int) * 8 - 1) then you have an overflow.

int x, y;
if (sign(x) == sign(y)){
    unsigned int ux = abs(x), uy = abs(y);    
    overflow = ux + uy >= (1 << (sizeof(int) * 8 - 1));
}

Better yet, let's write a template:

template <typename T> 
bool overflow(signed T x, signed T y){
    unsigned T ux = x, uy = y;
    return ( sign(x) == sign(y) && (ux + uy >= (1 << (sizeof(T) * 8 - 1)));
}
didierc
  • 14,572
  • 3
  • 32
  • 52