Detecting Signed Overflow in C/C++

Detecting signed overflow in C/C++

Your approach with subtraction is correct and well-defined. A compiler cannot optimize it away.

Another correct approach, if you have a larger integer type available, is to perform the arithmetic in the larger type and then check that the result fits in the smaller type when converting it back

int sum(int a, int b)
{
    long long c;
    assert(LLONG_MAX>INT_MAX);
    c = (long long)a + b;
    if (c < INT_MIN || c > INT_MAX) abort();
    return c;
}

A good compiler should convert the entire addition and if statement into an int-sized addition and a single conditional jump-on-overflow and never actually perform the larger addition.

Edit: As Stephen pointed out, I'm having trouble getting a (not-so-good) compiler, gcc, to generate the sane asm. The code it generates is not terribly slow, but certainly suboptimal. If anyone knows variants on this code that will get gcc to do the right thing, I'd love to see them.

How to detect integer overflow in C

You can predict signed int overflow but attempting to detect it after the summation is too late. You have to test for possible overflow before you do a signed addition.

It's not possible to avoid undefined behaviour by testing for it after the summation. If the addition overflows then there is already undefined behaviour.

If it were me, I'd do something like this:

#include <limits.h>

int safe_add(int a, int b) 
{
    if (a >= 0) {
        if (b > (INT_MAX - a)) {
            /* handle overflow */
        }
    } else {
        if (b < (INT_MIN - a)) {
            /* handle underflow */
        }
    }
    return a + b;
}

Refer this paper for more information. You can also find why unsigned integer overflow is not undefined behaviour and what could be portability issues in the same paper.

EDIT:

GCC and other compilers have some provisions to detect the overflow. For example, GCC has following built-in functions allow performing simple arithmetic operations together with checking whether the operations overflowed.

bool __builtin_add_overflow (type1 a, type2 b, type3 *res)
bool __builtin_sadd_overflow (int a, int b, int *res)
bool __builtin_saddl_overflow (long int a, long int b, long int *res)
bool __builtin_saddll_overflow (long long int a, long long int b, long long int *res)
bool __builtin_uadd_overflow (unsigned int a, unsigned int b, unsigned int *res)
bool __builtin_uaddl_overflow (unsigned long int a, unsigned long int b, unsigned long int *res)
bool __builtin_uaddll_overflow (unsigned long long int a, unsigned long long int b, unsigned long long int *res)

Visit this link.

EDIT:

Regarding the question asked by someone

I think, it would be nice and informative to explain why signed int overflow undefined, whereas unsigned apperantly isn't..

The answer depends upon the implementation of the compiler. Most C implementations (compilers) just used whatever overflow behaviour was easiest to implement with the integer representation it used.

In practice, the representations for signed values may differ (according to the implementation): one's complement, two's complement, sign-magnitude. For an unsigned type there is no reason for the standard to allow variation because there is only one obvious binary representation (the standard only allows binary representation).

Signed Integer value overflow in C++?

Because signed overflow/underflow are classified as undefined behavior, compilers are allowed to cheat and assume it can't happen (this came up during a Cppcon talk a year or two ago, but I forget the talk off the top of my head). Because you're doing the arithmetic and then checking the result, the optimizer gets to optimize away part of the check.

This is untested code, but you probably want something like the following:

if(b != 0) {
    auto max_a = std::numeric_limits<int64_t>::max() / b;
    if(max_a < a) {
        throw std::runtime_error{"overflow"};
    }
}
return a * b;

Note that this code doesn't handle underflow; if a * b can be negative, this check won't work.

Per Godbolt, you can see your version has the check completely optimized away.

Detecting if an unsigned integer overflow has occurred when adding two numbers

You could use

if((a + b) < a)

The point is that if a + b is overflowing, the result will be trimmed and must be lower then a.

Consider the case with hypothetical bound range of 0 -> 9 (overflows at 10):

b can be 9 at the most. For any value a such that a + b >= 10, (a + 9) % 10 < a.

For any values a, b such that a + b < 10, since b is not negative, a + b >= a.

Catch and compute overflow during multiplication of two large integers

1. Detecting the overflow:

x = a * b;
if (a != 0 && x / a != b) {
    // overflow handling
}

Edit: Fixed division by 0 (thanks Mark!)

2. Computing the carry is quite involved. One approach is to split both operands into half-words, then apply long multiplication to the half-words:

uint64_t hi(uint64_t x) {
    return x >> 32;
}

uint64_t lo(uint64_t x) {
    return ((1ULL << 32) - 1) & x;
}

void multiply(uint64_t a, uint64_t b) {
    // actually uint32_t would do, but the casting is annoying
    uint64_t s0, s1, s2, s3; 
    
    uint64_t x = lo(a) * lo(b);
    s0 = lo(x);
    
    x = hi(a) * lo(b) + hi(x);
    s1 = lo(x);
    s2 = hi(x);
    
    x = s1 + lo(a) * hi(b);
    s1 = lo(x);
    
    x = s2 + hi(a) * hi(b) + hi(x);
    s2 = lo(x);
    s3 = hi(x);
    
    uint64_t result = s1 << 32 | s0;
    uint64_t carry = s3 << 32 | s2;
}

To see that none of the partial sums themselves can overflow, we consider the worst case:

        x = s2 + hi(a) * hi(b) + hi(x)

Let B = 1 << 32. We then have

            x <= (B - 1) + (B - 1)(B - 1) + (B - 1)
              <= B*B - 1
               < B*B

I believe this will work - at least it handles Sjlver's test case. Aside from that, it is untested (and might not even compile, as I don't have a C++ compiler at hand anymore).

Detecting signed integer multiplication overflow in C

You can do something like this.

int reverse(int n) {
    // 1st overflow checking...
    // Check if the absolute value is greater than INT32_MAX.
    // I converted "int" to "long" to get correct overflow value.
    if (n < 0 && (long) n * -1l > INT32_MAX) {
        return 0;
    }
    
    int res = 0;
    // Convert to absolute value.
    int tmp = n < 0 ? n * -1 : n;
    
    while (tmp > 0) {
        // Get the right most digit and add it to the current result.
        res += tmp % 10;
        // Remove the right most digit.
        tmp /= 10;
        
        // "tmp" still has remaining numbers.
        if (tmp > 0) {
            // 2nd overflow checking...
            // Check if reversed value will be greater than INT32_MAX when appending 0 to right most.
            // I converted "int" to "long" to get correct overflow value.
            if ((long) res * 10l > INT32_MAX) {
                return 0;
            }
            
            // Append 0 to right most value of result.
            // If result is equal to 0, do not append 0.
            res *= res == 0 ? 1 : 10;
        }
    }
    
    // Return result.
    // If original value is negative, return negative result value..
    return n < 0 ? res * -1 : res;
}

---

Related Topics