Hatena::ブログ(Diary)

やた@はてな日記

2014-02-26

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

整数除算のエラーとしては 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'
浮動小数点例外 (コアダンプ)

syohexsyohex 2014/02/27 12:08 理解されていると思いますが, あまり知らない人や関連サイトを見ない人のために
(INT_MIN / -1)の結果を 2の補数では表現することができない、ということを
言及しておいた方がいいと思います. 実在するかは不明ですが, 1の補数のシステム
では, (INT_MIN / -1)の結果を表現することはできます.

あと浮動小数点例外(SIGFPE)が発生するのは、除算は FPU(浮動小数点ユニット)で
実行しているためです. CPUで除算命令を実装しているというのはほとんどなくて,
組み込み向けの CPUでは FPUが積んでいないこともあるので, ソフトウェアで
実装されたランタイムルーチンを使うことがよくあります.

s-yatas-yata 2014/02/27 13:05 ご指摘ありがとうございます.

2 の補数について書き足しておきました.
どうやら 2 の補数が当然という考えが染み付いてしまっているようです.

除算に FPU が使われているという件については,なんとなくそうなのかなーとは思っていたのですが,これではっきりしました.
あらためまして,ありがとうございます.

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証