Strange behaviour of integer overflow

Question

I created the following code for finding the answer to the coin problem. This involves finding minimum number of coins of given k denominations (where each such coins are in infinite supply) to form a target sum n. In particular I have investigated the case where k=5, denominations = {2,3,4,5,6} and target sum n=100.

Code:

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

The output to this code that I received is -2147483632. Clearly some kind of overflow must be occurring so I decided to output INF+1. And I got INT_MIN as the answer. But I had also remembered that often while outputting some numbers beyond the int range there was no such problem.

I decided to output 1e11 and to my surprise the answer was still 1e11. Why is this happening, please help.

signed integer overflow is undefined, In practice it may still appear to work, thats why your experiment didnt help to resolve the issue. UB that appears to work is still UB — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Oct 21, 2020 at 12:21
1e11 has the type double and is a value that is perfectly representable by double. — NathanOliver
– NathanOliver, Commented Oct 21, 2020 at 12:28
@Damien -- since it's defined at file scope, all of the elements in values are set to 0. Explicitly setting values[0] to 0 doesn't change anything. — Pete Becker
– Pete Becker, Commented Oct 21, 2020 at 13:02

Damien · Accepted Answer · 2020-10-21 12:56:18Z

1

Here:

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

For example, for x=3 and coins[0]=2, you add values[1] + 1.

However, values[1] = INT_MAX. Then, you get an undefined behavior when performing this calculation.

You can solve the issue with INF = INT_MAX - 1;

answered Oct 21, 2020 at 12:56

Damien

4,8844 gold badges20 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

eerorika · Accepted Answer · 2020-10-21 12:30:29Z

If your program performs arithmetic on signed integers that produces result that is outside the range of representable values - i.e. if such operation overflows - such as in the case of INT_MAX + 1 then the behaviour of the program is undefined.

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

1e11 is a floating point literal. Floating point types have different range of representable values from int, and different requirements regarding overflow.

Collectives™ on Stack Overflow

Strange behaviour of integer overflow

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related