5

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.

Jarod42
  • 203,559
  • 14
  • 181
  • 302
jcarpenter2
  • 5,312
  • 4
  • 22
  • 49
  • 3
    Possible duplicate of [How to detect integer overflow?](https://stackoverflow.com/questions/199333/how-to-detect-integer-overflow) – Germán Feb 28 '18 at 08:07
  • Are there any constraints on the numerical values? Min/Max? Anything? (If so you could possibly knock it down to 1 comparison) In the general case one subtraction isn't bad, maybe you could use bit masks to determine if the two numbers ANDED together would create UINT64T_MAX, bitwise operations are pretty cheap but I don't know of AND would correctly account for overflow. – Garrigan Stafford Feb 28 '18 at 08:42
  • The title says `unsigned int`s and `uint_max` but the code says `uint64_t`. Which exactly did you mean? – jotik Feb 28 '18 at 11:59
  • If there's a "little-known CPU feature" then your compiler ought to know about it – M.M Feb 28 '18 at 20:06
  • @M.M that's true, but compilers aren't magic - you do need to "not prevent" them from applying any given optimization. See "as if" rule. – jcarpenter2 Feb 28 '18 at 21:32

2 Answers2

9

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.

zneak
  • 134,922
  • 42
  • 253
  • 328
1
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.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483