内容更新

intの型は32bitであると限定しました。(2020,10/26 18:19)
補数って？のとこに3つ有る中の一つの2の補数表現を扱うというように表記を改めました。(2020,10/26 18:26)
オーバーフローの処理は未定義なので表記を改めました。(2020,10/27 21:24)
オーバーフローに関して表記を再度改めました。(2020,11/09 19:01)

* ~~補数表現~~、**負数表現**に改めました。(2021,3/17 11:17)

なんで`int`(32bit)の最大値は`2147483647`なんですか？

なんかもっとこう、1000000000とかのがきれいでいいよね。なんでこんなに不便そうな値を使うのか？ということに焦点を当てて行くよ。

そもそも`int`とは？

まず、大前提として、computer内部では、基本的に2進数で動いています。
なんでなのかと言うと、(参考:コンピューターで2進数が使われる理由 )

ノイズに強い
表現が容易
演算が簡単
2値で状態を表現できる

などなどがあるそうです。2進数のデメリットも合わせて知っておきたいという人は上記のURLを確認してみてください。

ということで、computerは2進数で動いてると確認できたので、intも2進数で表現されてるんだなと言うのは容易に想像できますね。

ここで、問題なのが、例えば、10進数で、4桁だとすると、負の数を考えなければ、0~9999まで全部で、10000個の表現ができます。

ですね。つまり、桁数によって表現できる範囲が変わるよということ。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);
}

出力は何になってるでしょうか？

これがどうなっているのか？を考えます。

上記のINTの最大値に1を足すと32bit以上は無視しましたね。それがここでも行われています。

どういうことかと言うと、

a = 00000000 00000000 00000001 01010100
charは8bitしか見ないので、

c =                            01010100
として評価しています。

これは、84ですね、それに対応するTが出力されているということですね。

まとめ

オーバーフローは処理系によっては巡回する挙動を示し、それがbit演算が要因であると確認した。(2020,11/09 19:01)

大きい方にキャストすると符号拡張が行われている
小さい方にキャストするとキャストした方のbit以上は無視されるので情報が失われる場合がある

お疲れさまでした :)

参考資料