ABC192Dでオーバーフローを判定する必要がある問題が出題された。 オーバーフローを判定する必要がある問題は数回解いたが、毎回ググっていてよくない。 そこで整数の加算・乗算のオーバーフローを判定する方法をメモする。 言語はGCC C++、競技プログラミングで使用することを想定している。
まずはオーバーフローの条件式を学ぶ。 ↓のブログを読んでみた。
64ビット整数のオーバーフロー判定についてのメモ – tomeapp http://tomeapp.jp/archives/2301
立式
$a, b$を固定長整数、$MAX$をその型がとる最大値とする。
オーバーフローが起こる条件式は次のように変形できる。
加算のとき。 $$a + b > MAX$$ $$a > MAX - b$$
乗算のとき。 $$a b > MAX$$ $$a > MAX / b$$
実装
$a, b$の型をT
とする。
まずT
の最大値を調べる。
std::numeric_limits::max
関数でT
の最大値を取得する()。
例えばstd::numeric_limits<int>::max()
はint
型の最大値を返す。
cout << numeric_limits<int>::max() << "\n"; // 2147483647
では関数として実装する。
// AとBの加算がオーバーフローするか返す template <typename T> constexpr bool isAddOverflow(T a, T b) { return a > numeric_limits<T>::max() - b; } // AとBの乗算がオーバーフローするか返す template <typename T> constexpr bool isProdOverflow(T a, T b) { if(b == 0) return false; return a > numeric_limits<T>::max() / b; } // このコードブロックのコードはCC0でライセンスする // https://creativecommons.org/publicdomain/zero/1.0/legalcode
テスト
試しに実行してみた。
#include <iostream> using namespace std; // AとBの加算がオーバーフローするか返す template <typename T> constexpr bool isAddOverflow(T a, T b) { return a > numeric_limits<T>::max() - b; } // AとBの乗算がオーバーフローするか返す template <typename T> constexpr bool isProdOverflow(T a, T b) { if(b == 0) return false; return a > numeric_limits<T>::max() / b; } int main() { cin.tie(0); ios::sync_with_stdio(0); cout << numeric_limits<int>::max() << "\n"; // 2147483647 cout << isAddOverflow<int>(2e5, 2e5) << "\n"; cout << isAddOverflow<int>(2e9, 2e9) << "\n"; cout << isProdOverflow<int>(2e2, 2e2) << "\n"; cout << isProdOverflow<int>(2e5, 2e5) << "\n"; cout << isProdOverflow<int>(2e9, 2e9) << "\n"; // 0 // 1 // 0 // 1 // 1 }
備考
- アンダーフローは考慮していない。
- $MAX / b$が割り切れないのとき、小数点以下が切り捨てられて正しく動作しないのではないか?反例を考えたが思い浮かばなかった。