綾小路龍之介の素人思考

[c言語] 数学的に無矛盾な(32ビットで桁あふれ無し)足し算ではエラーが出ないというint型の罠

int型は32ビットなので表現できるのは-2^31から2^31-1までの整数。純粋に数学的に33ビット目を使わなければならない事情が出てきても、33ビット目の箱は用意されていないので桁あふれがおきて、数学的には間違った答えが出る。このときはエラーが出るだろう。2^32-1に1足すと-2^31になる。たとえば下のようなプログラムでそれがわかる。C言語は2進数での代入に未対応なので16進数で代入してる。わかりにくいかもしれないが、まずフツーの数学。2^32-1は2進数でどうかけるか。

| 2 ^ 31 = 1 * 2^31 + 0 * 2^30 + 0 * 2^29 + 0 * 2^28
|        + 0 * 2^27 + 0 * 2^26 + 0 * 2^25 + 0 * 2^24
|        + 0 * 2^23 + 0 * 2^22 + 0 * 2^21 + 0 * 2^20
|        + 0 * 2^19 + 0 * 2^18 + 0 * 2^17 + 0 * 2^16
|        + 0 * 2^15 + 0 * 2^14 + 0 * 2^13 + 0 * 2^12
|        + 0 * 2^11 + 0 * 2^10 + 0 * 2^ 9 + 0 * 2^ 8
|        + 0 * 2^ 7 + 0 * 2^ 6 + 0 * 2^ 5 + 0 * 2^ 4
|        + 0 * 2^ 3 + 0 * 2^ 2 + 0 * 2^ 1 + 0 * 2^ 0
| 1      = 0 * 2^31 + 0 * 2^30 + 0 * 2^29 + 0 * 2^28
|        + 0 * 2^27 + 0 * 2^26 + 0 * 2^25 + 0 * 2^24
|        + 0 * 2^23 + 0 * 2^22 + 0 * 2^21 + 0 * 2^20
|        + 0 * 2^19 + 0 * 2^18 + 0 * 2^17 + 0 * 2^16
|        + 0 * 2^15 + 0 * 2^14 + 0 * 2^13 + 0 * 2^12
|        + 0 * 2^11 + 0 * 2^10 + 0 * 2^ 9 + 0 * 2^ 8
|        + 0 * 2^ 7 + 0 * 2^ 6 + 0 * 2^ 5 + 0 * 2^ 4
|        + 0 * 2^ 3 + 0 * 2^ 2 + 0 * 2^ 1 + 1 * 2^ 0

とすれば、2^nの係数を取り出して2進数が作れる。ということでそれぞれ下のようになる。

| ( 2 ^ 31 )_{10} = ( 1000 0000 0000 0000 0000 0000 0000 0000 )_{2}
| (      1 )_{10} = ( 0000 0000 0000 0000 0000 0000 0000 0001 )_{2}
| ( 2^31-1 )_{10} = ( 0111 1111 1111 1111 1111 1111 1111 1111 )_{2}

ここまでは数学的なお話。どこも違ってない。さて、ここからはコンピュータのお話。2進数での足し算も10進数での足し算も筆算の手順はあまり変わらない。(2^32-1)_{10}+(1)_{10}の計算結果は下のようになる。数学的にも無矛盾な結果だ。しかし、計算結果の最上位ビットが1になってるという点に注意してほしい。

| ( 2^31-1 )_{10} = ( 0111 1111 1111 1111 1111 1111 1111 1111 )_{2}
| (      1 )_{10} = ( 0000 0000 0000 0000 0000 0000 0000 0001 )_{2}
| ( 2 ^ 31 )_{10} = ( 1000 0000 0000 0000 0000 0000 0000 0000 )_{2}

計算結果をprintf( "%d", a )などで確認したい場合がある。下のようなプログラムを作ってみた。

int main( void ){
  int q = 0x7FFFFFFF;
  printf( "2 ^ 31 - 1     = %d\n", q );
  printf( "2 ^ 31 - 1 + 1 = %d\n", q + 1 );
}

数学的には無矛盾な結果であり、桁あふれもおきないのに、2行目は負の数が表示されたと思う。このからくりはこうだ。int型の変数では32ビット目(最上位ビット)は正負の判定にも使われて(数を表すのにも使われる)、0なら正で1なら負なので、結果は負の数ということだ。だから負の数が表示される。コンピュータは今の計算を行った結果、正の数同士の足し算から正の数を得たけど、int型の変数に結果を収めた場合、結果を負の数として理解する。ここが問題なのである。負の数と理解される、という点だ。だから変数には正解が入っているけど、出力するときには不正解を出力するということである。

| 0x7FFFFFFF = 0111 1111 1111 1111 1111 1111 1111 1111
| 0x00000001 = 0000 0000 0000 0000 0000 0000 0000 0001
| 0x80000000 = 1000 0000 0000 0000 0000 0000 0000 0000

ソーシャルブックマーク

  1. はてなブックマーク
  2. Google Bookmarks
  3. del.icio.us

ChangeLog

  1. Posted: 2007-06-23T16:02:29+09:00
  2. Modified: 2007-06-23T15:17:25+09:00
  3. Generated: 2017-08-09T23:09:26+09:00