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

Question

5

假设我有两个整数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具有但鲜为人知的功能。

- jcarpenter2

3

可能是重复的问题，与“如何检测整数溢出？”（How to detect integer overflow?）相关。 - Germán

数值上有任何限制吗？最小值/最大值？其他限制吗？（如果有可能可以将其降至1个比较）。在一般情况下，减法不算糟糕，也许您可以使用位掩码来确定两个数相与是否会创建UINT64T_MAX，按位操作非常便宜，但我不知道AND是否会正确地处理溢出。 - Garrigan Stafford

标题上写着“unsigned int”和“uint_max”，但代码中却写着“uint64_t”。你到底想表达的是哪一个？ - jotik

如果有一个“鲜为人知的CPU功能”，那么你的编译器应该知道它。 - M.M

@M.M 这是真的，但编译器并不是魔法 - 你需要“不阻止”它们应用任何给定的优化。请参见“好像”规则。 - jcarpenter2

2个回答

1

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

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

但是如果您有任何疑问，请检查生成的汇编代码。

- Bathsheba

@MarcGlisse：所以他们确实这样做了，我正要点赞那个答案。 - Bathsheba

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- zneak · Accepted Answer

在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++委员会成员正在考虑改变这一点)。

一些编译器提供非标准方法来检查各种算术函数的溢出情况，不仅限于加法，也不仅限于有符号数字。如果您能承受失去可移植性的代价，使用它们进行添加功能的增强可能值得研究。对于无符号加法溢出的特定情况，在一些非平凡的情况下，性能可能完全相同或可以忽略不计，因此可能不值得失去可移植性。