int型の最大値は0xffffffffではない

正体不明のバグが全然取れなくて、ずっと困ってたんですけど、実は処理自体は間違ってなくて、int型の最大値を表現するのに

#define INF (0xffffffff)

みたいなマクロを使ってたせいでした。

実はint型の場合 0xffffffff = -1 です。

どうして-1になるのかは、多分プログラマ的には常識だと思うんですけど、初学者が中途半端に16進数を使うとよく陥りそうな(というか陥った)ミスだったのでメモしておきます。原因が既に分かる人は時間の無駄なのでブラウザバック。

まずint型が取りうる値(今更ですがこのエントリはint型=4byteの環境を想定しています)は、

-2,147,483,648〜2,147,483,648

-2,147,483,648〜2,147,483,647

これは既知。「約20億まで入る」みたいな認識だと思います。

計算機の中で負数を表現する場合、最上位ビットを使って表していて、0なら正数、1なら負数となる。

これも既知。これだけ分かっていれば実は解ける。既知の情報しか使っていないんですよ。だけど思考停止して16進数を使うと痛い目を見るんですよね。

だから正解は0xffffffffではなく0x7fffffff。

もう大体分かったと思うんですけど、ここからちゃんとした解説。

0xffffffffを2進数で表すと、

1111,1111,1111,1111,1111,1111,1111,1111

となり、このとき最上位ビットの値は1です。つまり負数となってしまうんですね。

では正しい最大値はどうなるか。

0111,1111,1111,1111,1111,1111,1111,1111

最上位ビットは0で、それ以外のビットは全て1なので、これが最大値です。

これを16進数で表す場合、

0111 = 0x7

なので0x7fffffffとなります。

ではなぜ 0xffffffff = -2,147,483,648 ではないのか？

感覚的には最上位ビットのみ0のときに20億なら全ビットが1なら-20億になりそうなものですが、ここも単純な理由があります。

例えば、

int a = 0xffffffff + 1;

とすると、aに格納されるのは0x100000000のはずですが、4byteを超えて桁が溢れてしまうため、実際には0x00000000が格納されます。だから-1になっているんですよね。(ただしこの説明はあまり正しくないと思う)

もし0xffffffffが-2,147,483,648だった場合、

int a = -2,147,483,648 + 1; printf(“a=%d”,a);

実行結果はa=0となってしまいます。

逆に 0x7fffffff + 1 (=0x80000000)は、

1000,0000,0000,0000,0000,0000,0000,0000

最上位ビットのみが1なので-2,147,483,648となり、ちゃんと(？)オーバーフローします。

こういうバグ作っちゃうと全然気付かないので、マクロの定義はきちんとしようと思いました(小並感)