How to Detect Unsigned Integer Overflow

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.

How to detect integer overflow in C [duplicate]

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).

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.

Warnings (or other means) to identify potential unsigned integer overflows

For MSVC, you can enable warnings such as C26451 while building by enabling "Code Analysis" in the project's (or file's) properties¹:

Alternatively, you can run that code analysis on an open/active file at any time using the "Run Code Analysis on File" command from the "Build" menu (or Ctrl+Shift+Alt+f7).

---

You can enable this option on the command-line using the /analyze switch; however, you will need to specify the code analysis "plugins" (which ship with Visual Studio) to use (a typical option would be along the lines of /analyze:plugin EspxEngine.dll). An overview of these is given on this Microsoft web-page, in the "Analysis plugin options" section. The following paragraph appears particularly relevant:

When you build on the command line, you can use the Esp.Extensions
environment variable to specify EspXEngine extensions. For
example:
set Esp.Extensions=ConcurrencyCheck.dll;CppCoreCheck.dll;

---

¹ But note, this option will increase build times considerably, which may become problematic for large projects.

Detecting a unsigned integer overflow in a c function

You can detect overflow, or more precisely wrap around, by comparing the value with a computed maximum before the operation:

#include <stdio.h>
#include <stdint.h>

uint64_t collatz(uint64_t n) {
    uint64_t count = 0;

    if (n == 0) {
        return count;
    }

    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            if (n > (UINT64_MAX - 1) / 3) {
                printf("overflow!\n");
                return UINT64_MAX;
            }
            n = (3 * n) + 1;
        }
        if (count == UINT64_MAX) {
            printf("too many iterations!\n");
            return UINT64_MAX;
        }
        count++;
    }
    return count;
}

Detect Integer Overflow Using If Statement [duplicate]

It depends on what sort of operation you are using and what are the types of the operands.

e.g. if you want to detect an overflow after addition, and both operands are unsigned integers, then an overflow will have occurred if the result is less than the sum of both operands.

bool overflow;
if (a+b < a)
   overflow = true;
else
   overflow = false;

For signed integers, you can refer to the excellent post here

How to get a warning in GCC for unsigned integer overflow instead of wrap-around?

Overflow of signed integers invokes undefined behavior, while unsigned integer overflow is well defined.

For unsigned integers, overflow occurs as if the values were computed modulo one more than the maximum value of the given type. Put another way, if the type is n bits wide, then only the low order n bits of the result are retained. This is not actually overflow but is referred to as wraparound.

This is spelled out in section 6.5p9:

The range of nonnegative values of a signed integer

type is a subrange of the corresponding unsigned integer
type, and the representation of the same value in each type
is the same. A computation involving unsigned operands can
never overflow, because a result that cannot be represented by
the resulting unsigned integer type is reduced modulo the
number that is one greater than the largest value that can
be represented by the resulting type.

Because this behavior is well defined, it doesn't make sense for the compiler to trigger a warning.

In the case of your second example:

long x = 2147483647U * 3U; 

The multiplication is done on unsigned types, so the mathematical result 6442450941 wraps around to 2147483645, which is within the range of a long. There's no overflow (just wraparound) and no out-of-range conversion, so no warning.

---

Related Topics