Блог пользователя fedimser

Проверка переполнения
Автор fedimser, 12 лет назад, По-русски

Всем привет.
На Codeforces Round 184 (Div. 2) моё решение взломали из-за переполнения во время умножения. В связи с эти вопрос. Если есть две переменные типа int64, то как проверить, происходит ли переполнение при вычислении a*b?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Например, так:

double INF = ...
if ((double)a * b > INF)
{
}
→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

Можно, например, так:

c = a * b;

if (c / a != b) {

// переполнение

}

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Или так: log(a) + log(b) > log(INF)

→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Приведённые выше примеры либо могут быть неточными (double), либо со знаковыми типами вызывают неопределённое поведение (c = a * b).

Если числа неотрицательные, то проверить можно примерно так:

bool will_overflow = b != 0 && a > LLONG_MAX / b;

Однако полезность такой проверки мне представляется сомнительной. Допустим, что логика решения этой проверки не требует и нам нужно вывести как раз это a * b. Теперь мы вставляем проверку и на каком-то тесте обнаруживаем потенциальное переполнение. И что теперь делать, раз ответ всё равно не вычислен? С таким же успехом можно и вообще не проверять. Вывод: надо просто писать решение так, чтобы возможность переполнения никогда не возникала.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Зато не так редко возникает ситуация, когда в коде if(a*b<=n)... значения переменных a, b и n порядка 1018. И тогда действительно вместо умножения втупую надо писать через деление.

    → Ответить