Check if the sum of two unsigned ints is larger than uint_max

Question

Suppose I have two integers x and y, and I want to check whether their sum is larger than UINT_MAX.

#define UINT64T_MAX std::numeric_limits<uint64_t>::max()

uint64_t x = foo();
uint64_t y = foo();
bool carry = UINT64T_MAX - x < y;

That code will work, but I want to know if there's a more efficient way to do it - possibly using some little-known feature that CPUs have.

Answer 1

In C++, unsigned integer overflow has well-defined behavior. If you add two unsigned integers and the result is smaller than either one, then the calculation overflowed. (The result will always be smaller than both, so it doesn't matter which one you check.)

#define UINT64T_MAX std::numeric_limits<uint64_t>::max()

uint64_t x = foo();
uint64_t y = foo();
uint64_t z = x + y;
bool carry = z < x;

I'm confident that this is the best way to do it in portable, well-defined C++. Clang and GCC both compile this trivial example to the optimal sequence of two amd64 instructions (add x, y; setc carry).

This does not generalize to signed integer overflow, as signed integer overflow is undefined behavior (although some C++ committee members are looking to change that).

Some compilers offer non-standard ways to check for overflow after various arithmetic functions, not just for addition, and not just for signed numbers. Using them for that added functionality might be worth investigating if you can afford to lose portability. For the specific case of unsigned addition overflow, performance is likely to be identical or negligibly faster in some non-trivial cases and it is probably not worth losing portability.

Answer 2

auto t = x + y;
bool x_y_overflows_unsigned = t < x || t < y; // Actually, the second check is unnecessary.

would be hard to beat and is possibly clearer insofar that using subtraction with unsigned types often introduces bugs.

But if you are in any doubt, check the generated assembly.