c++: int 小于 INT_MAX 时溢出

Question

我写了如下代码。

#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;

long long int N, K;



int main() {
    cin >> N >> K;

    long long int result = 0;
    int IntResult = 0;

    for (long long int i = K; i <= N + 1; i++) {
        result += 1 + (N + 1 - i) * i;
        IntResult += 1 + (N + 1 - i) * i;
    }

    cout << result % (1000000000 + 7) << endl;
    cout << IntResult % (1000000000 + 7) << endl;
    return 0;
}

当我输入“141421 35623”时，这段代码输出如下。

141421 35623
220280457
619089693

正确答案是“220280457”。 int的结果是错误的。

我将 cout 放入 for 循环中并检查了 IntResult 的值。

然后我发现IntResult在一个for循环中变成了负值。溢出来了！

但是为什么呢？ int 的最大值为“2147483648”。它大于“220280457”。

而for循环中的过程只是加法，所以我无法理解为什么会溢出。

请帮帮我！

Answer 1

在您的循环中，表达式 1 + (N + 1 - i) * i（被评估为 long long int）快速且频繁地 变得大于 INT_MAX，当您尝试将其添加到 (int) result.

时，这会导致整数溢出

将快速 'check' 添加到您的代码中，如下所示，将证明这一点：

int main()
{
    cin >> N >> K;
    long long int result = 0;
    int IntResult = 0;
    int count = 0;
    for (long long int i = K; i <= N + 1; i++) {
        // Check for intermediate overflow potential...
        long long int lli = 1LL + (N + 1LL - i) * i;
        if (lli > INT_MAX) cout << lli << " (" << ++count << ")"  << endl;
        result += 1 + (N + 1 - i) * i;
        IntResult += 1 + (N + 1 - i) * i;
    }
    cout << result % (1000000000 + 7) << endl;
    cout << IntResult % (1000000000 + 7) << endl;
    return 0;
}

当我运行在我的平台（32 位 int 和 64 位 long long int）上使用您给定的输入（141421 和 35623)，"overflow check" 行实际上发生了 88,498 次 ！这是最后三行输出：

...
2147524241 (88498)
220280457
619089693

此外，即使上面检查的加数本身可能不会溢出 int，将其添加到 result 中的现有（可能非零）值的结果可能仍然这样做。实际上，将 'check' 行更改为：

if ((lli + result) > INT_MAX) cout << lli << " (" << ++count << ")"  << endl;

显示循环在每次迭代时溢出！

Answer 2

您在第一次迭代时溢出。

1 + (N + 1 - i) * i

小于

(N - i)*i

第一次迭代：

(141421-35623)*35623

哎呀已经溢出了，这是有符号整数的 UB。

IntResult % (1000000000 + 7)

之后发生，并且没有任何意义，因为 IntResult 包含未知值。

c++: int 小于 INT_MAX 时溢出

c++: int overflows when it is smaller than INT_MAX

c++

integer-overflow