デジタル情報の表現（1）数(整数)

# はじめに

* プログラミングを始める人に
* コンピュータの一連の動作を具体的に示し
* プログラミング技能を効率的に習得することをねらう

---

# すべて0と1でできている

* 情報とみなせるデータはたくさん
    * 数/整数、小数
    * 文字
    * 音
    * 画像/字体、色
    * これらの組み合わせ
* 本稿では特にこの中の数/**整数**について学ぶ

---

# 二進数: 二進法によって表記された数

* 二進法: 数の表現形式の1つ。0と1の数字だけ使用
    1. 13 : 十進数
    1. (1101)<sub>2</sub>: 二進数
    1. 1101: 二進数の略記

    * 13= (1101)<sub>2</sub> = 1101

---

# 十進数から二進数へ

例題）十進数13を二進数で表記

* 2で割った商と余りを求める
* 商が0になるまで繰り返す
* すべての余りを<ins>右から左に並べ直す</ins>

```math
\begin{array}{rrrr}
2 ) & 13 & & \\ \hline 
2 ) & 6  & ...1 & 商6 余り1 \\ \hline 
2 ) & 3  & ...0 & 商1 余り0 \\ \hline 
2 ) & 1  & ...1 & 商1 余り1 \\ \hline 
    & 0  & ...1 & 商0 余り1 \\ \hline 

\end{array}
```

* つまり、13 ＝ 1101
* 全ての数は2で割ると、割り切れて余りが0になるか、割り切れずに余りが1になるかしかありません
    * 商は小さな数になるので、繰り返すことで商は必ず0にたどり着きます


---

# ここで、数当てゲーム

二進数の計算を利用した数当てゲーム

* 0から15の数を思い浮かべます
* これから4回、以下の表AからDを使って質問をします
* 各表に思い浮かべた数があれば「はい」なければ「いいえ」です
* これであなたの思い浮かべた数はぴたりと当てられます

表A
<table>
<tr><td>1</td><td>3</td><td>5</td><td>7</td></tr>
<tr><td>9</td><td>11</td><td>13</td><td>15</td></tr>
</table>

表B
<table>
<tr><td>2</td><td>3</td><td>6</td><td>7</td></tr>
<tr><td>10</td><td>11</td><td>14</td><td>15</td></tr>
</table>

表C
<table>
<tr><td>4</td><td>5</td><td>6</td><td>7</td></tr>
<tr><td>12</td><td>13</td><td>14</td><td>15</td></tr>
</table>

表D
<table>
<tr><td>8</td><td>9</td><td>10</td><td>11</td></tr>
<tr><td>12</td><td>13</td><td>14</td><td>15</td></tr>
</table>

* これは0－15までの数ならすべて当てられます。不思議ですよね？

---
# 13を思い浮かべていた場合

次のような計算をしています。

* 各表に含まれていた場合を1、含まれない場合を0
* 含まれていた表の最初の数の積を求める
* 計算結果を全て足します
* 具体的に...
    1. 表Aに13は含まれる(1) x 1 ＝ 1
    1. 表Bに13は含まれない(0) x 2 ＝ 0
    1. 表Cに13は含まれる(1) x 4 ＝ 4
    1. 表Dに13は含まれる(1) x 8 ＝ 8
    1. これらを全て足すと... <b>1 x 8 + 1 x 4 + 0 x 2 + 1 x 1</b> = 8 + 4 + 0 + 1 ＝ 13
* この計算はいったいどういう意味があるのでしょうか？
* 実は、これは二進法の計算そのものです

---

# 二進法の計算は何をしていたのか


```math
\begin{array}{rrrr}
2 ) & 13 & & \\ \hline 
2 ) & 6  & ...1 & 商6 余り1 \\ \hline 
2 ) & 3  & ...0 & 商1 余り0 \\ \hline 
2 ) & 1  & ...1 & 商1 余り1 \\ \hline 
    & 0  & ...1 & 商0 余り1 \\ \hline 
\end{array}
```
* 3 つの計算式がある
    * 13 = 6 x 2 + 1
    * 6 = 3 x 2 + 0
    * 3 = 1 x 2 + 1
* この4式をまとめると...
    * 13 =      6                    x 2 + 1 
    *    = (    3          x 2 + 0 ) x 2 + 1 
    *    = (   (1 x 2 + 1) x 2 + 0 ) x 2 + 1
    *    ここで、x 2 を順番に外から展開する
    *    =     (1 x 2 + 1) x 2 x 2 + 0 x 2 + 1
    *    =     1 x 2x2x2 + 1 x 2x2 + 0 x 2 + 1( x 1)
    *    =  <b>1</b> x  <ins>8</ins>   + <b>1</b> x  <ins>4</ins>  + <b>0</b> x <ins>2</ins> + <b>1</b> x <ins>1</ins>  
        * 下線が引かれた値は、各表の最初の数であり
        * 太字の値は、各表のはいかいいえで割り当てた数と対応しています
        * 先ほどの思い浮かんだ数を計算した式ですよね！

* この数当てゲームは見方を変えて、8g、4g、2g、1gの分銅で重さを計っているとみなしてもよい
    * 分銅の組み合わせで、わからない重さを15gまでの範囲でなら特定できる

---

# 解説

<table>
<tr></tr>
<tr>
<td>

* 右の表は0から15までの十進数を、二進数で示しています
    * 表Aに書かれている数は、二進数の1桁目が［１］である数の集まり
    * 表Bに書かれている数字は、二進数の2桁目が［１］である数の集まり
    * 表Cに書かれている数字は、二進数の3桁目が［１］である数字の集まり
    * 表Dに書かれている数字は、二進数の4桁目が［１］である数字の集まり
* そのため、表Aから表Dまでに該当する数があるか、ないかと問いかけることにより、二進数の各桁が［１］であるか、［０］であるかを知ることができます
* その4桁の二進数を十進数に変換して、数を当てています



</td>
<td>

|十進数|表D|表C|表B|表A|
|--:|--:|--:|--:|--:|
|0|0|0|0|0|
|1|0|0|0|<font color="red">1</font>|
|2|0|0|<font color="red">1|0|
|3|0|0|<font color="red">1|<font color="red">1|
|4|0|<font color="red">1|0|0|
|5|0|<font color="red">1|0|<font color="red">1|
|6|0|<font color="red">1|<font color="red">1|0|
|7|0|<font color="red">1|<font color="red">1|<font color="red">1|
|8|<font color="red">1|0|0|0|
|9|<font color="red">1|0|0|<font color="red">1|
|10|<font color="red">1|0|<font color="red">1|0|
|11|<font color="red">1|0|<font color="red">1|<font color="red">1|
|12|<font color="red">1|<font color="red">1|0|0|
|13|<font color="red">1|<font color="red">1|0|<font color="red">1|
|14|<font color="red">1|<font color="red">1|<font color="red">1|0|
|15|<font color="red">1|<font color="red">1|<font color="red">1|<font color="red">1|


</td>
</tr>
</table>

---

# 発展

* 数当てゲームを0-31までの数当てができるように拡張したい
    * どのように表Eを用意し、
    * 表Aから表Dを修正すればよいだろうか？

* 以下の表を使ってよい

|十進数|表E|表D|表C|表B|表A|
|--:|--:|--:|--:|--:|--:|
|16|<font color="red">1</font>|0|0|0|0|
|17|<font color="red">1</font>|0|0|0|<font color="red">1</font>|
|18|<font color="red">1</font>|0|0|<font color="red">1|0|
|19|<font color="red">1</font>|0|0|<font color="red">1|<font color="red">1|
|20|<font color="red">1</font>|0|<font color="red">1|0|0|
|21|<font color="red">1</font>|0|<font color="red">1|0|<font color="red">1|
|22|<font color="red">1</font>|0|<font color="red">1|<font color="red">1|0|
|23|<font color="red">1</font>|0|<font color="red">1|<font color="red">1|<font color="red">1|
|24|<font color="red">1</font>|0|<font color="red">1|0|0|0|
|25|<font color="red">1</font>|<font color="red">1|0|0|<font color="red">1|
|26|<font color="red">1</font>|<font color="red">1|0|<font color="red">1|0|
|27|<font color="red">1</font>|<font color="red">1|0|<font color="red">1|<font color="red">1|
|28|<font color="red">1</font>|<font color="red">1|<font color="red">1|0|0|
|29|<font color="red">1</font>|<font color="red">1|<font color="red">1|0|<font color="red">1|
|30|<font color="red">1</font>|<font color="red">1|<font color="red">1|<font color="red">1|0|
|31|<font color="red">1</font>|<font color="red">1|<font color="red">1|<font color="red">1|<font color="red">1|


---

# まとめ

```math
\begin{array}{ll} 
 n & = ... + a_3 \times 8 + a_2 \times 4 + a_1 \times2 + a_0 \times 1 \\ 
   & = ... + a_3 \times 2^3 + a_2 \times 2^2 + a_1 \times 2^1 + a_0 \times 2^0 \end{array}
```

* あらゆる数(整数)は0と1で表現できることを示した: 二進法
* 0と1で表された二進数から元の十進数に復元できることを示した:数当てゲーム