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

はじめに

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

---

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

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

---

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

• 二進法: 数の表現形式の1つ。0と1の数字だけ使用

  1. 13 : 十進数
  2. (1101)₂: 二進数
  3. 1101: 二進数の略記
  • 13= (1101)₂ = 1101

---

十進数から二進数へ

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

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

\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

1	3	5	7
9	11	13	15

表B

2	3	6	7
10	11	14	15

表C

4	5	6	7
12	13	14	15

表D

8	9	10	11
12	13	14	15

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

---

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

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

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

---

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

\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)
  • = 1 x 8 + 1 x 4 + 0 x 2 + 1 x 1
    * 下線が引かれた値は、各表の最初の数であり
    * 太字の値は、各表のはいかいいえで割り当てた数と対応しています
    * 先ほどの思い浮かんだ数を計算した式ですよね！

• この数当てゲームは見方を変えて、8g、4g、2g、1gの分銅で重さを計っているとみなしてもよい

  • 分銅の組み合わせで、わからない重さを15gまでの範囲でなら特定できる

---

解説

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

---

発展

• 数当てゲームを0-31までの数当てができるように拡張したい

  • どのように表Eを用意し、
  • 表Aから表Dを修正すればよいだろうか？

• 以下の表を使ってよい

十進数	表E	表D	表C	表B	表A
16	1	0	0	0	0
17	1	0	0	0	1
18	1	0	0	1	0
19	1	0	0	1	1
20	1	0	1	0	0
21	1	0	1	0	1
22	1	0	1	1	0
23	1	0	1	1	1
24	1	0	1	0	0
25	1	1	0	0	1
26	1	1	0	1	0
27	1	1	0	1	1
28	1	1	1	0	0
29	1	1	1	0	1
30	1	1	1	1	0
31	1	1	1	1	1

---

まとめ

\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で表された二進数から元の十進数に復元できることを示した:数当てゲーム