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

<font color="Red">内容更新</font>

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




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

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


## そもそも`int`とは？

まず、大前提として、computer内部では、基本的に2進数で動いています。
なんでなのかと言うと、(参考:[コンピューターで2進数が使われる理由](http://www.yamamo10.jp/yamamoto/lecture/2006/1E/30th/html/node5.html) )

1. ノイズに強い
2. 表現が容易
3. 演算が簡単
4. 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進数を補数表現と呼ばれる表現方法を用います。


> <font color="Red">負数表現には、主な方式をあげると、「符号＋絶対値方式」、「げたばき表現」、 「2の補数表現」の3つがある。[参考資料](http://www.cc.kyoto-su.ac.jp/~kbys/kiso/number/negative.html)</font>

<font color="Red">今回はこの中の2の補数表現について取り上げます。(2020,10/26 18:26) </font>


### 補数って？

先程、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の計算ができるようになったのでもう少し踏み込んでみます。また、キャストしたときに何が起こっているのかも、知っときましょう。


---
## オーバーフロー??


<font color="Red">そもそも、大前提として、オーバーフローやアンダーフロー時の動作はC言語の規格としては未定義です。なので、これを考える理由はないかもなのですが、一応、bitとキャストの観点から考察してみましょう。(2020,11/09 19:01)
 </font>


> 整数演算で値の範囲を超えるときのオーバーフローやアンダーフロー時の動作はC言語の規格としては未定義です。実装依存で異なる場合もありますが、多くの処理系で、エラーを出すことなく循環します。1バイト（8ビット）の符号無しの値255に+1すると0になる。符号付きの値127に+1すると-128になる。このように+1を続けると表す値が循環することになります。[参考資料](http://www.ibe.kagoshima-u.ac.jp/edu/gengo0/p4.html)

上記から多くの処理系では、未定義ではあるものの、巡回する動作をすることがわかります。
では、巡回する動作に対して、なぜこのような挙動を示すのか？それについて考えてみます。

まず、`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)
```

となり、符号拡張により符号の変動が無いことが確認できました。

これを用いると、例えば、

足し算


```c
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

```

引き算

```c
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

```
となっています。

これは符号拡張の観点から見ても、正確性は保たれてますね。

----
## 小さい型にキャストするとどうなるのか？

以下の出力を考えましょう。

```c
int main(){
    int a = 340;
    char c = (char)a;

    printf("%c\n",c);
}
```

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

```c
T
```


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


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

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


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

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

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


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

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

## お疲れさまでした :)

## 参考資料

* [整数の表現](http://ocw.kyushu-u.ac.jp/menu/faculty/09/4/3.pdf)
* [数値に関する諸問題](https://www.k-cube.co.jp/wakaba/server/numerical_problem.html)
* [整数型とビット操作](https://www.cc.kyoto-su.ac.jp/~yamada/programming/bit.html)
* [算術演算と変数～演算子と変数の型](https://dev.grapecity.co.jp/support/powernews/column/clang/004/page03.htm)