Detecting integer overflow

[Ole Nielsby]

Given two longs:

long a = ...;
long b = ...;

What's the simplest/fastest way of performing a simple
operation on longs and detecting overflow?

long c = a + b; // but branch on overflow

One way is to perform the operation with long long:

long long temp = (long long)a + b;
c = (long)temp;
if ((long long)c != temp) goto blast;

but it seems a bit strange that I'd have to use long long
for all computations, to deal with the relatively rare case
of overflow.

 

[Krishanu Debnath]

Given two longs:

long a = ...;
long b = ...;

What's the simplest/fastest way of performing a simple
operation on longs and detecting overflow?

long c = a + b; // but branch on overflow

if (b <= LONG_MAX - a) {
c = a + b;
}
else {
// Overflow
}

TODO: a and b are both negative.

One way is to perform the operation with long long:

long long temp = (long long)a + b;
c = (long)temp;

Remember : If temp cannot be represented in long you are invoking
implementation defined behavior.

Just check if temp belongs to [LONG_MIN, LONG_MAX]

Krishanu

 

[Roman S.]

Given two longs:

long a = ...;
long b = ...;

What's the simplest/fastest way of performing a simple
operation on longs and detecting overflow?

long c = a + b; // but branch on overflow

One way is to perform the operation with long long:

long long temp = (long long)a + b;
c = (long)temp;
if ((long long)c != temp) goto blast;

but it seems a bit strange that I'd have to use long long
for all computations, to deal with the relatively rare case
of overflow.

Would the following work?

long c = a + b;
if (a > 0 && b > 0 && c < 0)
Overflow();

 

[Frederick Gotham]

Ole Nielsby posted:

What's the simplest/fastest way of performing a simple
operation on longs and detecting overflow?

Off the top of my head, you could test for a negative answer where a positive
answer was expected, and vice versa -- but that's only after the overflow has
taken place. E.g.:


long a=3000000000,b=4000000000;

long c = a*b;

if(c < 0) throw Overflow();

Ofcourse, you want to make sure beforehand that overflow doesn't invoke
undefined behaviour:

COMPILE_TIME_ASSERT( std::numeric_limits<long>::modulo );

 

[Ole Nielsby]

[...]
What's the simplest/fastest way of performing a simple
operation on longs and detecting overflow?

long c = a + b; // but branch on overflow

if (b <= LONG_MAX - a) {c = a + b;} else {/*Overflow*/}
TODO: a and b are both negative.

That's the problem. It would take several conditional jumps
to test using nothing but longs, and conditional jumps are
bad for performance.

Remember : If temp cannot be represented in long you are invoking
implementation defined behavior.

I think this doesn't matter, as long as a long is returned. If c doesn't
represent temp, the next comparison will detect it:

Thanks to those who suggested other solutions - but I'll stick
with the long long way for now unless something more elegant
comes up - as far as I can see, the other suggestions involve
multiple conditional jumps. I just hoped there would be an
intrinsic function or some language feature I had overlooked
(like the checked/unchecked keywords of C#) that allowed
me to get code like:

add eax, ebx
jo overflow

from the C++ compilers (assuming register variables).
It puzzles me that this trivial asm is so complicated
in C++.

Regards/Ole

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

That's the problem. It would take several conditional jumps
to test using nothing but longs, and conditional jumps are
bad for performance.

So you want to branch without jumping?

I think this doesn't matter, as long as a long is returned. If c doesn't
represent temp, the next comparison will detect it:

And this is not a conditional jump? And the extension to long long and the
comparison takes no time? Maybe your way is faster than the others
suggested, but you can't know for sure.

 

[Ole Nielsby]

And this is not a conditional jump?

I was just pointing out that my solution has fewer conditional
jumps than the others.

And the extension to long long and the comparison takes no
time?

Generally, such operations are a lot faster than conditional
jumps because they are predictable and don't mess up the
instruction pipelines the way conditional jumps do.

Maybe your way is faster than the others suggested, but you
can't know for sure.

Naturally, testing will be required to make the best decision.
BTW, the outcome is likely to depend much on the CPU type
- I guess the "long long" solution will be the fastest on 64 bit
architectures that can handle long long natively, while the
others might be faster on 32 bit CPUs, depending on how
the compiler implements the long long comparison.

Regards/Ole N.

 

[=?ISO-8859-15?Q?Juli=E1n?= Albo]

I was just pointing out that my solution has fewer conditional
jumps than the others.
Generally, such operations are a lot faster than conditional
jumps because they are predictable and don't mess up the
instruction pipelines the way conditional jumps do.

But you are no choosing between a way without jumps and one with jumps, just
between more or less jumps. It's no so easy to predict the
predictability

 

[Steve Pope]

An easier test than true overflow is whether your int
(let's say it's 32 bits) has exceeded half its range,
either in the positive or negative direction:

int overflow = 1 & ((x>>30) ^ (x>>31));

Think of it as an overflow of a 31 bit integer. In
many algorithms if the magnitude of the value has become this
large, it will truly overflow soon.

Steve