内容更新
- intの型は32bitであると限定しました。(2020,10/26 18:19)
- 補数って？のとこに3つ有る中の一つの2の補数表現を扱うというように表記を改めました。(2020,10/26 18:26)
- オーバーフローの処理は未定義なので表記を改めました。(2020,10/27 21:24)
- オーバーフローに関して表記を再度改めました。(2020,11/09 19:01)
なんでint(32bit)の最大値は2147483647なんですか？
なんかもっとこう、1000000000とかのがきれいでいいよね。なんでこんなに不便そうな値を使うのか？ということに焦点を当てて行くよ。
そもそもintとは？
まず、大前提として、computer内部では、基本的に2進数で動いています。
なんでなのかと言うと、(参考:コンピューターで2進数が使われる理由 )
- ノイズに強い
- 表現が容易
- 演算が簡単
- 2値で状態を表現できる
などなどがあるそうです。2進数のデメリットも合わせて知っておきたいという人は上記のURLを確認してみてください。
ということで、computerは2進数で動いてると確認できたので、intも2進数で表現されてるんだなと言うのは容易に想像できますね。
ここで、問題なのが、例えば、10進数で、4桁だとすると、負の数を考えなければ、0~9999まで全部で、10000個の表現ができます。
0000
0001
:
9998
9999
ですね。 つまり、桁数によって表現できる範囲が変わるよということ。10進数で1桁だと、0~9なので、10個の表現ができます。また、ここで、n桁だとすると、10^n(10のn乗)の表現方法があることもわかりますね。
では、intはというと、4byte、つまり32bitと定義されています。このbitが桁数に対応しているので、32桁あって、intは２進数なので、2^32!
となり、2^32 = 4294967296なので、表現の幅としては、4294967296で最大値は、0も考慮して、4294967296 - 1 = 4294967295。
あれ、なんか違う........
そもそもintってマイナスの値もあるので間違っているのは、当然ですね。
ちなみに、負の数以外を扱うunsigned intに関しては、最大値が等しくなっているので、すべての数字を表現できて、計算はあながち間違ってなそうですね。
では、intでマイナスを考慮すれば良さそうということがわかったので、マイナスも考慮して考えていきます。
2進数でマイナスってどう表現するの？
そもそも2進数の表現方法はといえば、
10進数 <-> 2進数
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
2進数は0と1を用いて、表現されていて、1を超えると桁が上がってる(桁が増える)ことも確認できます。(10進数も同じですね)
表現がややこしくなるのでここからN進数表記を(_N)で表現することにします
これは数式で表すと、
X = ABCD(_2)
= A*2^(n-1) + B*2^(n-2) + C*2^(n-3) + D*2^(n-4) ( <ー 10進数) (式1)
と表現できます。試しに、n=4として、7とかで確認してみてください。
では、2進数のマイナスはというと、2進数を補数表現と呼ばれる表現方法を用います。
負数表現には、主な方式をあげると、「符号＋絶対値方式」、「げたばき表現」、 「2の補数表現」の3つがある。参考資料
今回はこの中の2の補数表現について取り上げます。(2020,10/26 18:26)
補数って？
先程、2進数ではX=....と表すことができていたので、
q進数では、
Xq = A(n-1)A(n-2).....A1A0(_q)
= A(n-1)*q^(n-1) + A(n-2)*q^(n-2) + ... + A1*q^1 + A0*q^0 ( <- 10進数)(式2)
と表せます。
ここで、
Yq = q^n - Xq (式3)
と表した、YqをXqのqの補数といいます。
またq^nはq進数で(n + 1)桁になっているので注意。
(式3)から、
Xq + Yq = q^n
= 1000000000 (式3-2)
<---n--->
1 n
桁 桁
と表されていることがわかります。
この結果から、
ある2進数で表現されたNを考えたときに、-Nというのは、
N + (-N) = 0
となるはずですね。
ここで、N=0011(_2)として考えてみると、(Nは10進数では3)
-N = 1101(_2)となる。
これは、N = 0011 の各bitを入れ替えて(1100)、＋1を加えた値に一致している。
これは、
0011(_2) + 1101(_2) = 10000(_2)
であり、最上位の1を無視すると、0000(_2)となっている。
また、(式3)からーNはNの2の補数に一致することもわかる
例えば、2の補数表現された、4bitの2進数を考えると、正の数と0は、
0000(_2)~0111(_2)つまり0(_10)~7(_10)で表せて、
負の数は1111(_2)~1000(_2)つまり、-1(_10)~-8(_10)を表現することができる。
ここで、2の補数表現されたn桁の2進数Nを10進数に変換するには、
N = -A(n-1)*2^(n-1) + A(n-2)*2^(n-2)+ .... + A(0)*2^0
で表現できます。これは、3(_10)で試してみてください。
またここから、最上位のbitに関しては、符号を表している、というのもわかりますね。
ここから、intの最大値、最小値について考えられそうですね。
重要なので、-N(_2)の求め方をまとめておくと、
-N(_2) = (N(_2)のbitを反転させたもの) + 1
実際に計算してみる
intの最大値、最小値
INT_MAX = 01111111 11111111 11111111 11111111
= 0 * 1*2^(n-2) + 1*2^(n-3) + 1*2^(n-4) + ..... + 1*2^1 + 1*2^0
= 2^(n-1) - 1
= 2147483648 - 1 (n = 32を代入)
= 2147483647
INT_MIN = 10000000 00000000 00000000 00000000
= -2^(n-1)
= -2147483648
わかりやすく8つごとにbitをわけました。
上記のを見るときちんと求めたい値が出てきてますね。
これでタイトルは回収したので、もう終わりとしてもいいのですが、bitの計算ができるようになったのでもう少し踏み込んでみます。また、キャストしたときに何が起こっているのかも、知っときましょう。
オーバーフロー??
そもそも、大前提として、オーバーフローやアンダーフロー時の動作はC言語の規格としては未定義です。なので、これを考える理由はないかもなのですが、一応、bitとキャストの観点から考察してみましょう。(2020,11/09 19:01)
整数演算で値の範囲を超えるときのオーバーフローやアンダーフロー時の動作はC言語の規格としては未定義です。実装依存で異なる場合もありますが、多くの処理系で、エラーを出すことなく循環します。1バイト（8ビット）の符号無しの値255に+1すると0になる。符号付きの値127に+1すると-128になる。このように+1を続けると表す値が循環することになります。参考資料
上記から多くの処理系では、未定義ではあるものの、巡回する動作をすることがわかります。
では、巡回する動作に対して、なぜこのような挙動を示すのか？それについて考えてみます。
まず、INT_MAX + 1について見ていきます。
INT_MAX = 01111111 11111111 11111111 11111111
INT_MAX + 1 = 01111111 11111111 11111111 11111111
+ 00000000 00000000 00000000 00000001
---------------------------------------
1 00000000 00000000 00000000 00000000
= -2^32 (intのサイズ以上(32bit)は無視する)
になっていますね。つまり、最大値を超えると最小値になっていて、そのままくるくる巡回しているのではないか？
次に、INT_MIN - 1がどうなるのか?考えてみましょう。
bitではA-BではなくA+(-B)と扱うことに注意しましょう。
INT_MIN - 1 = 10000000 00000000 00000000 00000000
+ 11111111 11111111 11111111 11111111
---------------------------------------
1 01111111 11111111 11111111 11111111
= 2^31 - 1 (intのサイズ以上(32bit)は無視する)
実際には、未定義動作なので、内部でどのような挙動になっているのかはわかりませんが、bitの計算の観点から見ると、たしかに巡回するような動作を確認できました。
符号拡張? (大きい型にキャストしたときの処理について)
2の補数表現された、2進数には、符号拡張と呼ばれる性質があります。
これは、2の補数表現された、2進数では、正負関係なく、最上位bit(符号bit)と同じ値を持つbitを新たに付け加えても値が変化しないというものである。
3(_10)と-3(_10)を4bit、5bitで表した場合を考える、
0011(_2) = 0*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 3(_10)
00011(_2) = 0*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 3(_10)
1011(_2) = -1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 3(_10)
11011(_2) = -1*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = 3(_10)
となり、符号拡張により符号の変動が無いことが確認できました。
これを用いると、例えば、
足し算
long a = 42;
int b = 24;
long l = (long)b;
a + l = 66;
# これは、bitの世界から見ると、
a + l = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00101010
+ 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011000
--------------------------------------------------------------------------
00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000010
引き算
long a = 42;
int b = 24;
long l = (long)b;
a - l = 18;
# これは、bitの世界から見ると、
a + (-l) = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00101010
+ 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11101000
----------------------------------------------------------------------------
1 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00010010
となっています。
これは符号拡張の観点から見ても、正確性は保たれてますね。
小さい型にキャストするとどうなるのか？
以下の出力を考えましょう。
int main(){
int a = 340;
char c = (char)a;
printf("%c\n",c);
}
出力は何になってるでしょうか？
T
これがどうなっているのか？を考えます。
上記のINTの最大値に1を足すと32bit以上は無視しましたね。それがここでも行われています。
どういうことかと言うと、
a = 00000000 00000000 00000001 01010100
charは8bitしか見ないので、
c = 01010100
として評価しています。
これは、84ですね、それに対応するTが出力されているということですね。
まとめ
- オーバーフローは処理系によっては巡回する挙動を示し、それがbit演算が要因であると確認した。(2020,11/09 19:01)
- 大きい方にキャストすると符号拡張が行われている
- 小さい方にキャストするとキャストした方のbit以上は無視されるので情報が失われる場合がある