Проверка нескольких номеров для переполнения

Question

У меня проблемы с обнаружением переполнения. Я должен сделать программу, которая читает int c, а затем int n пар чисел, которые следует умножить. После умножения чисел вам нужно проверить, не является ли это переполнением целого числа или нет. Если это не переполнение, количество чисел умножается.

В C++;

Вот пример:

Введите: 3 2147483647 и 2147483647

+18446744073709551615 и 2

666013 и 1

Выходы:

4611686014132420609 

Overflow! 

666013 


fin>>c; 
for (i=1;i<=c;i++,p=0){ 
    fin>>a>>b; 
    p=a*b; 
    if (p/b==a) 
     fout<<p<<"\n"; 
    else 
     fout<<"Overflow"<<"\n"; 
} 




return 0; 
} 

Answer 1

Вы попали в ловушку, пытаясь использовать результат, чтобы проверить, произошло ли переполнение. На самом деле вы не можете этого сделать. Подписанное целочисленное переполнение имеет неопределенное поведение, поэтому, как только это произошло, вы уже ввернуты. Вы должны проверить overlow с помощью операндов, до операции.

Пусть max - максимально представимое целое число. Предполагая, что операнды положительны, a * b переполняется тогда и только тогда, когда a * b > max. Но вы не можете выполнить этот тест, потому что, если переполняется a * b, результат неприменим. Кроме того, мы знаем, что целое число больше max, поэтому тест всегда будет ложным.

Итак, как мы можем использовать уравнение, не используя результат a * b? Мы будем использовать магию математики, и мы получим эквивалентное уравнение: a > max/b. Мы используем только целочисленный оператор деления, который не переполняется, Nice! Теперь эквивалентность уравнений выполняется только тогда, когда b != 0. Попытка разделить max/0 будет ошибкой. Но мы знаем, что a * 0 не переполняется ни для каких a, так что мы можем тривиально реализовать этот частный случай.

Итак, что мы имеем:

int a, b; 
// don't forget to initialize 
if(b && a > INT_MAX/b) 
    // overflow, abort! 
else 
    // no overflow, proceed 

Это работает правильно только для положительных входов. Я оставлю его как упражнение для чтения, чтобы реализовать тест для всех целых чисел.