cpp

オーバーフローの判定

乗算

a*bの積を求める場合、オーバーフローの上限は

  • a*b > (型の上限値)

となります。
bが整数の場合、式変形すると

  • a > (型の上限値) / b

とできます。

ll safeMul(ll a, ll b, bool& overflow) {
  overflow = false;
  if (b > 0 ? a > INT64_MAX / b || a < INT64_MIN / b
            : (b < -1 ? a > INT64_MIN / b || a < INT64_MAX / b : b == -1 && a == INT64_MIN)) {
    overflow = true;
    return INT64_MAX;
  }
  return a * b;
}

GCCだと__int128という128bit型が使用できます。

関連問題