えびちゃんの日記

えびちゃん（競プロ）の日記です。

Re: オーバーフロー判定が分からない人のためのスライド

経緯

以下ではあんまり元ネタっぽい感じではなくなります。すみません。

紹介

こういう記事 があります。

紹介 2

GCC 拡張の話をします。 競プロの人々は平気で GCC 拡張を使うので、今さら避ける必要もないと思って書きます。 __int128 や __builtin_popcount などはよく使われていますよね。

__builtin_mul_overflow という関数があります。掛け算してオーバーフローするとき真です。 次のような感じで使えます。

long f(long x, long y) {
  long z;
  if (__builtin_mul_overflow(x, y, &z)) {
    // x * y がオーバーフローしたときの処理
  } else {
    // x * y がオーバーフローしなかったときの処理
    // このとき、z == x * y になっている
  }
}

便利ですね。

gcc.gnu.org

もちろん、mul 以外もあります。

注意

「オーバーフローしたらその型の最大値を返すような wrapper クラスを作りましょう」という発想に至ることはあります。 ただ、そのクラスで雑に計算すると、（多倍長で計算してから、その型の最大値と min をとったときの）結果と合わないことがあるので注意です。

次のような問題を考えます。

\(a, b, c\) が与えられます。 \(a\cdot b - c\) が \(2^{63}\) 未満ならその値を、そうでなければ overflow を出力してください。

  • \(0\le a, b, c \lt 2^{63}\)

たとえば、\( (a, b, c) = (2^{62}+1 ,2, 3)\) としてみると、\(a\cdot b \ge 2^{63}\) です。

\(2^{63}-1\) と min をとりながら計算するクラスでそのまま計算すると、\(2^{63}-4\) になってしまいます。 あるいは、\(a\cdot b\) がオーバーフローした時点で overflow と出力しても誤りです。

紹介 3

Rust、えらくて、整数に a.overflowing_mul(b) とか a.saturating_mul(b) のようなメソッドが用意されています。 前者は、計算結果と「オーバーフローしていたら true」の bool 値のペアが返されます。 後者は、オーバーフローしなければ計算結果、していたらその型の最大値（あるいは最小値）が返されます。

他にも checked_mul とか wrapping_mul とかいろいろあります。

doc.rust-lang.org

「大人しく Rust でも使ってろ」という思想が漏れていないか？