检查两个无符号整数的总和是否大于uint_max

Question

假设我有两个整数x和y,和我要检查他们的总和是否大于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;

该代码将起作用,但我想知道是否有更有效的方法 - 可能使用CPU具有的一些鲜为人知的功能.

Answer 1

在C++中,无符号整数溢出具有明确定义的行为.如果添加两个无符号整数且结果小于任一个,则计算会溢出.(结果总是小于两者,因此检查哪一个并不重要.)

#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;

我相信这是在便携式,定义良好的C++中实现这一目标的最佳方式.Clang和GCC都将这个简单的例子编译成两个amd64指令(add x, y; setc carry)的最佳序列.

这并不能推广到签署整数溢出,作为符号的整数溢出是未定义的行为(尽管一些C++委员会成员正在寻找改变这种状况).

一些编译器提供非标准方法来检查各种算术函数之后的溢出,而不仅仅是添加,而不仅仅是有符号数.如果您可以承受丢失便携性,那么将它们用于增加的功能可能值得研究.对于无符号除了溢出的特定情况下,表现很可能是相同的,或在一些不平凡的情况下可以忽略不计更快,它可能是不值得失去了便携性.

Answer 2

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

很难被击败，并且可能更清楚，因为对无符号类型使用减法通常会引入错误。

但如果您有任何疑问，请检查生成的程序集。