像无符号整数溢出一样行为，是什么原因造成的？

Question

我有一个函数，它生成指定数量的所谓“三角形数”。如果我在之后打印deque，数字会先增加，然后跳下来，再次增加。三角形数不应该随着i的增长而减小，因此必须发生某种溢出。我尝试通过添加以下代码来修复它：if(toPush > INT_MAX) return i - 1;，以尝试防止函数生成更多的数字（并返回它生成的数字），如果结果溢出。然而，这并没有起作用，输出仍然是不正确的（一段时间增加，跳下到较低的数字，然后再次增加）。我添加的代码似乎根本没有起作用，return语句没有被执行。有人知道这里发生了什么吗？

#include <iostream>
#include <deque>
#include <climits>
int generateTriangleNumbers(std::deque<unsigned int> &triangleNumbers, unsigned int generateCount) {
    for(unsigned int i = 1; i <= generateCount; i++) {
         unsigned int toPush = (i * (i + 1)) / 2;
         if(toPush > INT_MAX) return i - 1;
         triangleNumbers.push_back(toPush);
    }
return generateCount;
}

- Memento Mori

---

第一个让它不起作用的i的值是多少？如果您手动进行该特定计算，会观察到什么？ - Oliver Charlesworth

你如何期望任何数字都严格大于最大可能的数字呢？ - Mat

你应该检查计算的每个步骤。特别是，如果溢出发生在(i * (i + 1))中，之后就无法检测到它了。 - Björn Pollex

@Mat 我想作为一个测试，我会检查它是否大于 INT_MAX，但仍然使用 unsigned int。这样希望在数字增长到可能大于 unsigned int 的大小之前，能够发现问题。 - Memento Mori

@OliCharlesworth 我会尝试找出它发生的 i 值。 - Memento Mori

Answer 1

INT_MAX是signed int类型的最大值。它大约是unsigned int（UINT_MAX）最大值的一半。你计算toPush的值可能会比UINT_MAX高得多，因为你对这个值进行了平方运算（如果它接近于INT_MAX，结果将远大于toPush所能承受的UINT_MAX）。在这种情况下，toPush会绕过并导致比以前的值更小的值。

首先，你将INT_MAX与unsigned int类型做比较是有缺陷的，因为你的类型是unsigned int而不是signed int。其次，即使与UINT_MAX进行比较也是不正确的，因为它意味着toPush（比较表达式的左操作数）可以保存一个超过它的最大值的值，而这是不可能的。正确的方式是将生成的数字与以前的数字进行比较。如果它更低，你就知道发生了溢出，应该停止。

此外，你可能需要使用可以容纳更大范围值的类型（例如unsigned long long）。

- SomeWittyUsername

Answer 2

第92682个三角数已经大于UINT32_MAX。但罪魁祸首在于更早的计算i * (i + 1)时，对于第65536个三角数，计算就会溢出。如果我们使用带有本地bignum支持的Python来计算：

>>> 2**16 * (2**16+1) > 0xffffffff
True

糟糕。如果您检查存储的数字，您会看到序列回落到较低的值。为了尝试模拟标准对此情况的行为，在Python中：

>>> (int(2**16 * (2**16+1)) % 0xffffffff) >> 1
32768

这是第65536个三角数，你将看到的值是错误的。

检测溢出的一种方法是确保生成的数字序列是单调递增的；也就是说，如果第N个生成的三角数严格大于第(N-1)个三角数。

为避免溢出，您可以使用64位变量来同时生成和存储它们，或者如果需要大量的三角数，可以使用大数库。

- Michael Foukarakis

---

这个程序完美运行了。我没想到只要检查新数字是否大于上一个数字就可以了。我修改了代码，现在它能在适当的时间结束了。 - Memento Mori

Answer 3

在Visual C++中，即使在64位计算机上，int（当然还有unsigned int）也是32位的。

要使用64位值，请使用unsigned long long或uint64_t。

- Some programmer dude