Integer Overflow w/ Multiplication in C

Question

I've recently been messing around with C and have come to the concept of integer overloading. I'm trying to create a program that detects whether or not two 32 bit integers multiplied by each other will be able to fit into another 32 bit integer.

I understand the concept of integer overflow and how integers end up overflowing, but I'm stuck with figuring out the logic for this program. Here's what I have so far:

int main() {    
int min = INT_MIN;
int max = INT_MAX;

int num1, num2;
int x = num1 * num2;

printf("Please enter a number you would like to multiply: ");
scanf("%d", &num1);
printf("\nPlease enter a second number you would like to multiply: ");
scanf("%d", &num2);

if (num1 > max / num2){
    printf("\nOverflow! - first case\n");
}
else if (num2 > max / num1){
    printf("\nOverflow! - second case\n");
}
else if ((num1 > max - num2 && num2 > 0 ) || 
     (num1 < max - num2 && num2 < 0)){

    printf("\nOverflow! - third case\n");
}
else
    printf("\nNot Overflow!\n");

return 0;
}

As you can see, my program can detect some cases for overflow, but several other cases like -2 * 3 and -2 * -3 will get caught by my conditions.

So what I have will absolutely not work. What are good ways to go about solving this?

Test if arithmetic operation will cause undefined behavior may help. — chux
– chux, Commented Jan 23, 2019 at 2:52

Osiris · Accepted Answer · 2019-01-23 12:22:30Z

4

An integer overflows when a*b > INT_MAX or when a*b < INT_MIN.

This leads to the inequations:

If b > 0: a > INT_MAX/b or a < INT_MIN/b
If b < 0: a < INT_MAX/b or a > INT_MIN/b

So the condition which outputs if an int overflows is:

b>0 && (a>INT_MAX/b || a<INT_MIN/b) || b<0 && (a<INT_MAX/b || a>INT_MIN/b)

Since here INT_MIN/b could overflow itself (when b=-1) this should be checked seperately.

This is a rather long condition and should maybe be splitted up and put into a function:

int ismultoverflow(int a, int b)
{
    if(b > 0)
    {
        if(a>INT_MAX/b || a<INT_MIN/b)
        {
            return 1;
        }
    }
    else if(b < 0)
    {
        if(b == -1)
        {
            return a==INT_MIN;
        }

        if(a<INT_MAX/b || a>INT_MIN/b)
        {
            return 1;
        }
    }

    return 0;
}

Another approach would be to group the inequations into four domains rather than two:

If a > 0 and b > 0: a > INT_MAX/b
If a > 0 and b < 0: b < INT_MIN/a
If a < 0 and b > 0: a < INT_MIN/b
If a < 0 and b < 0: b < INT_MAX/a

which leads to a function where you do not have to handle a special case:

int ismultoverflow(int a, int b)
{
    if(a>0 && b>0 && a>INT_MAX/b)
    {
        return 1;
    }
    if(a>0 && b<0 && b<INT_MIN/a)
    {
        return 1;
    }
    if(a<0 && b>0 && a<INT_MIN/b)
    {
        return 1;
    }
    if(a<0 && b<0 && b<INT_MAX/a)
    {
        return 1;
    }

    return 0;
}

Of course if you could use types with larger width it is way less complicated (it is not guaranteed that long or long long are wider than int, but on many platforms this is the case):

int ismultoverflow(int a, int b)
{
    long x=a, y=b;

    if(x*y > INT_MAX || x*y < INT_MIN)
    {
        return 1;
    }

    return 0;
}

edited Jan 23, 2019 at 12:22

answered Jan 23, 2019 at 1:54

Osiris

2,83311 silver badges17 bronze badges

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

2 Comments

Alain Merigot Over a year ago

In last version, you probably meant long long instead of long. In most modern computers, long has the same size as int. It could also be possible to use double.

Osiris Over a year ago

@AlainMerigot At least on my machine (x86_64 linux with gcc) int is 32 bits and long is 64 bit, but that of course may differ. Even long long is not guaranteed to be wider than int, but I added it as possibility. Yes but I dislike the idea of solving int problems with floating point math, because in may cases this is a bad idea (currency for example).

Collectives™ on Stack Overflow

Integer Overflow w/ Multiplication in C

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related