オーバーフローを判定する

ABC192Dでオーバーフローを判定する必要がある問題が出題された。オーバーフローを判定する必要がある問題は数回解いたが、毎回ググっていてよくない。そこで整数の加算・乗算のオーバーフローを判定する方法をメモする。言語はGCC C++、競技プログラミングで使用することを想定している。

まずはオーバーフローの条件式を学ぶ。 ↓のブログを読んでみた。

６４ビット整数のオーバーフロー判定についてのメモ – 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
}