3

我有这个函数可以生成指定数量的所谓“三角形数”。如果我打印出双端队列后缀，数字会增加，向下跳，然后再次增加。随着 i 的上升，三角形的数字永远不会变低，所以一定会发生某种溢出。如果结果溢出，我尝试通过添加行if(toPush > INT_MAX) return i - 1;来尝试阻止函数生成更多数字（并返回它生成的数字）来修复它。但是，这不起作用，输出仍然不正确（增加一段时间，跳到较低的数字，然后再次增加）。我添加的行实际上似乎根本没有做任何事情。未达到退货。有谁知道这里发生了什么？

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

3 回答 3

2

INT_MAX是 的最大值signed int。unsigned int它大约是( )最大值的一半UINT_MAX。您的计算toPush可能会比UINT_MAX您对值的平方高得多（如果它接近INT_MAX结果将远远大于UINT_MAX您toPush可以容纳的值）。在这种情况下，toPush环绕并导致值小于前一个值。

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

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

于 2013-03-08T09:59:03.323 回答
1

第 92682 个三角形数已经大于UINT32_MAX。但这里的罪魁祸首要早得多，在i * (i + 1). 在那里，第 65536 个三角数的计算溢出。如果我们询问 Python 的原生 bignum 支持：

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

哎呀。然后，如果您检查存储的数字，您将看到您的序列回落到低值。为了尝试模仿标准对这种情况的行为的描述，在 Python 中：

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

这就是您将看到的第 65536 个三角形数的值，这是不正确的。

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

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

于 2013-03-08T09:58:22.027 回答
0

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

使用unsigned long long或uint64_t使用 64 位值。

于 2013-03-08T09:47:23.027 回答