Целочисленное переполнение с умножением в C - PullRequest
Новая
       43

Целочисленное переполнение с умножением в C

0 голосов
/ 23 января 2019

Я недавно возился с C и пришел к концепции целочисленной перегрузки.Я пытаюсь создать программу, которая определяет, смогут ли два 32-разрядных целых числа, умноженные друг на друга, соответствовать другому 32-разрядному целому числу.

Я понимаю концепцию переполнения целых чисел и как переполнения целых чисел, но я застрял с выяснением логики для этой программы.Вот что у меня получилось: 

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

Как видите, моя программа может обнаружить некоторые случаи переполнения, но некоторые другие случаи, такие как -2 * 3 и -2 * -3, будут обнаружены моимусловия.

Так что у меня абсолютно не получится.Как можно решить эту проблему?

1 Ответ

0 голосов
/ 23 января 2019

Целое число переполняется, когда a*b > INT_MAX или a*b < INT_MIN.

. Это приводит к неравенствам:

Если b > 0: a > INT_MAX/b или a < INT_MIN/b
Еслиb < 0: a < INT_MAX/b или a > INT_MIN/b

Итак, условие, которое выводится при переполнении int: 

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

Так как здесь INT_MIN/b может переполниться само (когда b=-1) это следует проверять отдельно.

Это довольно длинное условие, и его, возможно, следует разбить на части и поместить в функцию: 

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

Другим подходом будет группировка неравенствна четыре домена, а не на два:

Если a > 0 и b > 0: a > INT_MAX/b
Если a > 0 и b < 0: b < INT_MIN/a
Если a < 0 и b > 0: a < INT_MIN/b
Если a < 0 и b < 0: b < INT_MAX/a

, что приводит к функции, в которой вам не нужно обрабатывать особый случай: 

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

Конечно, если вы могли бы использовать типы с большей шириной, это намного менее сложно (не гарантируется, что long или long long шире, чем int, но на многих платформах это так): 

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

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

    return 0;
}
...