整数溢出的奇怪行为

Question

我创建了以下代码来寻找硬币问题的答案。这涉及找到给定 k 面额的硬币的最小数量（其中每个这样的硬币都是无限供应的）以形成目标总和 n。特别是我调查了 k=5、面额 = {2,3,4,5,6} 和目标总和 n=100.

的情况

代码:

#include<iostream>
#include<algorithm>
using namespace std;

int coins[5] = {2,3,4,5,6};
int values[101];
int n=100;
int k=5;
int INF = INT_MAX;

int main()
{
    for (int x=1;x<=n;x++)
    {
        values[x] = INF;
        for (int j=1;j<=k;j++)
        {
            if (x-coins[j-1]>=0)
            {
                values[x] = min(values[x],values[x-coins[j-1]]+1);
            }
        }
    }
    cout<<values[100];

    return 0;
}

我收到的此代码的输出是 -2147483632。显然一定发生了某种溢出，所以我决定输出 INF+1。我得到了 INT_MIN 作为答案。不过我也记得，经常输出一些超出int范围的数字时，并没有这个问题。

我决定输出1e11，令我惊讶的是答案仍然是1e11。为什么会这样，求助。

Answer 1

如果您的程序对有符号整数执行算术运算而产生的结果超出可表示值的范围 - 即如果此类运算溢出 - 例如在 INT_MAX + 1 的情况下，则程序的行为是未定义的.

I decided to output 1e11 and to my surprise the answer was still 1e11.

1e11 是一个浮点数。浮点类型与 int 具有不同的可表示值范围，并且对溢出有不同的要求。

Answer 2

这里：

 values[x] = min(values[x],values[x-coins[j-1]]+1);

例如，对于 x=3 和 coins[0]=2，您添加 values[1] + 1。

然而，values[1] = INT_MAX。然后，在执行此计算时会出现未定义的行为。

您可以通过 INF = INT_MAX - 1;

解决问题

整数溢出的奇怪行为

Strange behaviour of integer overflow

c++

integer-overflow

c++14