整数除算のオーバーフローについて

整数除算のエラーとしては 0 による除算が有名ですが，オーバーフローも致命的なエラーになるなりえるという話です．

（追記 2014-02-27） そもそも整数の演算におけるオーバーフロー時の動作は未定義なのですが，加算，減算，乗算のオーバーフローについては，オーバーフローした分が捨てられるという前提で使っていることがよくあります．本当はやっちゃ駄目なのでしょうが…．

具体的には，符号付き 32-bit 整数の除算で INT32_MIN / -1 となったとき，およびに符号付き 64-bit 整数の除算で INT64_MIN / -1 となったときにオーバーフローが起きます（※1）． 8-bit や 16-bit の整数については，演算時に int への暗黙的な型変換がおこなわれるため， C/C++ では問題になりません（※2）．明示的に 8/16-bit 向けの IDIV 命令を使えば，同様の問題が再現できると思います（※3）．

※1 （追記 2014-02-27） id:syohex さんがコメントにて指摘されているように，上述の組み合わせがオーバーフローになるのは， 2 の補数（ 2の補数 - Wikipedia ）を使っている環境において， INT32_MIN の絶対値が INT32_MAX より大きくなるからです． 2 の補数を使っていない環境であれば，違う結果になるかもしれません．

※2 （追記 2014-02-27） id:Assume さんがはてブで指摘されているように， int が 16-bit の環境であれば，符号付き 16-bit 整数の除算でも問題になるはずです．

※3 （追記 2014-02-27） Intel® 64 and IA-32 Architectures Software Developer's Manual で調べたことであり， x86 や x64 以外でどうなるかはわかりません．

また，同じ IDIV 命令を使う剰余算についても，上述の組み合わせでエラーになります．

ためしに，以下のようなソースコードを用意します．

#include <climits>
#include <iostream>
int main() {
  int x = INT_MIN;
  std::cout << (x / -1) << std::endl;
  return 0;
}

これをコンパイルして実行すると，以下のようになりました（Ubuntu 12.04）．ただし，コンパイラが頑張ってしまうと x / -1 の演算がおこなわれない可能性があります．

$ clang++ a.cpp
$ ./a.out
浮動小数点例外 (コアダンプ)

整数の除算なのに浮動小数点例外と出ているあたりは不思議（※4）ですけど，エラーになることは確認できました．

※4 （追記 2014-02-27） 整数の除算であっても　FPU が使われるからだと id:syohex さんにコメントをいただきました．整数の除算より浮動小数点数の除算が速いのも納得です．

除算を使うときは除数が 0 にならないように気を付けていましたけど，上述の組み合わせによるオーバーフローは落とし穴でした．今後はオーバーフローにも注意するようにします．

後の話は蛇足ですけど， g++ を使うと以下のようになりました．

$ g++ a.cpp
$ ./a.out
-2147483648

そこで，ソースコードを以下のようにすると落ちるようになりました．ただし，最適化オプションを付けると再び落ちなくなります．

#include <climits>
#include <iostream>
int main() {
  int x = INT_MIN;
  int y = -1;
  std::cout << (x / y) << std::endl;
  return 0;
}

さらに蛇足ですが， clang++ で最適化オプションを付けたときは，実行する度に違う結果が表示されました．

$ clang++ -O2 a.cpp
$ ./a.out
-901424984
$ ./a.out
1683933848
$ ./a.out
116451400
$ ./a.out
130056888
$ ./a.out
996577544

実験に使った g++ と clang++ のバージョンは以下の通りです．

$ g++ --version
g++ (Ubuntu/Linaro 4.6.4-1ubuntu1~12.04) 4.6.4
Copyright (C) 2011 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ clang++ --version
clang version 3.3 (tags/RELEASE_33/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix

（追記 2014-02-27） clang には -fsanitize=signed-integer-overflow というオプションがあり，これを使うと以下のように出力されます．

$ clang++ -fsanitize=signed-integer-overflow a.cpp
$ ./a.out 
a.cpp:6:19: runtime error: division of -2147483648 by -1 cannot be represented in type 'int'
浮動小数点例外 (コアダンプ)