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时，这会导致整数溢出。

在你的代码中添加一个快速的"检查"，如下所示，将证明这一点：

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

当我使用给定的输入(141421和35623(在我的平台(32位int和64位long long int(上运行此代码时，"溢出检查"行实际上发生了88498次！以下是最后三行输出：

...
2147524241 (88498)
220280457
619089693

此外，即使上面检查的加数本身可能不会溢出int，但将其添加到result中现有(可能为非零(值的结果仍然可以做到这一点

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

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

Answer 2

您在第一次迭代时溢出。

1 + (N + 1 - i) * i

小于

(N - i)*i

第一次迭代：

(141421-35623)*35623

Whoops已经溢出，这是有符号整数中的UB。

IntResult % (1000000000 + 7)

随后发生，由于IntResult包含未知值，因此没有任何意义。