bool代数と論理回路超入門1 | 2進数とその計算

数学とコンピュータ Advent Calendarの初日です！
Qiitaに居るような人には数学あんまり人気ないんじゃないかと思って初日で登録したら，
Sanoさんのおかげか一瞬で埋まったのを見て超びびっています．
自分は数理物理学の院生で，最近はLaTeX以外のコードはほとんど書かないのですが頑張ります．

カレンダーを見ると，コンピュータ「で」数学をやる方が多い気がしますが，
あまり気にせず，コンピュータ「の」数学を簡単なところから展開してみたいと思います．

そもそも何やるの？

自分は高校生のとき，C++のプログラミング入門の本を片手に単純なプログラムを学んでいたのですが，¹

1. コードの意味は分かる
2. コンパイルして実行すると色々計算して思った通りの結果を返してくれる
3. コンピュータは電気で動いて，０と１しか分からないらしい

という理解の状況でした．
そこで，**コードと01の間は一体どういう理屈で動いているのか？？**ということが長年の疑問だったのですが，
大学に入って「論理回路」²，「コンピュータアーキテクチャ」という講義をうけたらその疑問が解消したので，
簡単に解説してみたいと思います．

内容としては大学でComputer Scienceを学んでいる人は常識のようなことですが，
「コードと01の間」というところに焦点を当てながら書けたらと思います．
自分は数学の人間でもあるので，数学的にもある程度ちゃんと書けたら良いなと思ってます．
（数式が難しいと感じる方は飛ばして読んでもらって構いません．
また，かなり丁寧に書いているつもりなので，
「こんなの当たり前だろ」と思う方は飛ばしながら読んでもらっても構いません．）
当然1回ではすべてを書くことはできないので，連載形式にしたいなと考えています．

bool代数

bool代数というのはジョージ・ブールさんが創始した数学の分野の1つで，
$S = \{0, 1\}$とすることで，³コンピュータを構成している回路のうち，
「組み合わせ回路」とよばれている回路とbool代数の式を対応づけることができます．
コンピュータ言語にtrueとfalseの変数を表す型としてboolean型があるものが多いですが，
その型の名前はここに由来しています．

数を0と1だけで表す

10進法

私たちが普段使っている数字は10進数という数字の表し方（記数法という）で，
0から9の10個の数字を並べて表します（位取り記数法という）．
また，1, 10, 100, 1000のように10倍になるごとに桁が増えていきます．
このことを式で表すと，$S = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$，
数$a\in\mathbb{N}$⁴の10進表記を$(a_j)_{j=0}^{m-1}\in S^m$としたとき，⁵

$$a = \sum_{j=0}^{m-1} a_j\cdot 10^j$$

が成立します．⁶
具体的には，$a = 1374$という数字は1と3と7と４をこの順番に並べた表し方をしますが，
これは$(a_3, a_2, a_1, a_0) = (1, 3, 7, 4)$として， ⁷

\begin{align*}
a &= a_3\times 10^3 + a_2\times 10^2 + a_1\times 10^1 + a_0\times 10^0\\
&= 1\times 1000 + 3\times 100 + 7\times 10 + 4\times 1\\
&= 1374
\end{align*}

というように計算することができます．⁸
このように，$n$種類の数字を$m$個並べて数を表す記数法を$n$進法といいます．

2進法

さて，それでは「0と1だけで」，すなわち$n = 2,\ S = \{0, 1\}$として数を表してみましょう．
数式だと

$$a = \sum_{j=1}^{m-1} a_j\cdot 2^j\tag{$\ast$}$$

となります．具体的に$a = 1011$という2進数を計算してみましょう．
$(a_3, a_2, a_1, a_0) = (1, 0, 1, 1)$として，

\begin{align*}
a &= a_3\times 2^3 + a_2\times 2^2 + a_1\times 2^1 + a_0\times 2^0\\
&= 1\times 8 + 0\times 4 + 1\times 2 + 1\times 1\\
&= 11
\end{align*}

という計算で，2進数の1011は10進数の11と対応することが分かりました．

10進数と2進数の変換

10進数と2進数はどのように変換できるのでしょうか？
当然コンピュータは一瞬でやってくれますが，仕組みを理解するために筆算の方法を考えてみましょう．
と言っても1から考えるのは大変なので，筆算の方法を見て，
そのアルゴリズムがどうしてうまく行くのかを考えましょう．
まずは10進数の795を2進数に変換していきたいと思います．

795 ( 1 ↑ #== 795 % 2
397 ( 1 ↑ #== 397 % 2
198 ( 0 ↑ #== 198 % 2
 99 ( 1 ↑ #== 198 % 2
 49 ( 1 ↑ #== 99 % 2
 24 ( 0 ↑ #== 24 % 2
 12 ( 0 ↑ #== 12 % 2
  6 ( 0 ↑ #== 6 % 2
  3 ( 1 ↑ #== 3 % 2
  1     ↑
  →→→→→→

これが10進数から2進数への変換の筆算の方法です．
まず795を書き，それを2で割った商397を下に書き，2で割った余り1を右側に書きます．
同じことを397に対して行い，商198と余り1を得ます．
同様に商が1になるまで繰り返します．
最後に一番下の1から右側に並んだ0と1の列を下から読むと，
それが得たかった2進数表記，つまり1100011011になります．
逆の2進数から10進数に変換するには上の($\ast$)の式に代入すればいいので，検算してみましょう．

\begin{align*}
&\quad\,1\cdot 2^9 + 1\cdot 2^8 + 1\cdot 2^4 + 1\cdot 2^3 + 1\cdot 2^1 + 1\cdot 2^0\\
&= 512 + 256 + 16 + 8 + 2 + 1\\
&= 795
\end{align*}

と確かに795になりました．（0の桁の項は省略しました．）
さて，このアルゴリズムがうまくいく理由を，この結果を用いながら具体的に見ていきましょう．
上の筆算を次のような式を順々に計算しながら書いていったものと考えると分かりやすいでしょう．

\begin{align*}
(795 \cdot 2^0) + 0 &=795\\
(397 \cdot 2^1) + (1 \cdot 2^0) &= 795\\ 
(198 \cdot 2^2) + (1 \cdot 2^1 + 1 \cdot 2^0) &= 795\\
(99 \cdot 2^3) + (0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0) &= 795\\
&\;\vdots\\
(1 \cdot 2^9) + (1 \cdot 2^8 + 0 \cdot 2^7 + \cdots + 1\cdot 2^1 + 1 \cdot 2^0) &= 795
\end{align*}

各行の式の左辺の1番目の括弧がまだ10進数の部分，2番目の括弧が2進数に変換できた部分になっていて，
2進数の下の桁から少しずつ計算していって，どの行も和は795になっていることが分かります．
（こういう不変量を保ちながら計算していくアルゴリズムってCSの方でもなんか名前がありましたよね？なんでしたっけ？）

数式でちゃんと書いておくと，$a_0$を変換する10進数，$(b_j)$を2進数の各桁とすると，

\begin{align*}
a_n &= \frac{a_{n-1} - b_{n-1} \cdot 2^{n-1}}{2}\\
b_n &= a_{n-1} \bmod 2\\
a_0 &= a_n \cdot 2^n + \sum_{j=0}^{n-1} b_j \cdot 2^j
\end{align*}

の漸化式を順次計算していく形になります．⁹
$n$は1以上の整数で，停止性は$a_n = 0$となるところで止めれば大丈夫です．
10進数と2進数の変換は最初は苦労しますが，慣れればそのうち暗算できるようになります．

固定長と可変長

有名なことですが，2進数の桁数のことをビット(bit)といいます．
また，8bitの塊で 1 バイト(byte)です．
ここまでは2進数の桁は自由に取ってきましたが，
桁数をあらかじめ固定するやり方もあります．
というか，コンピュータが数字を扱うときは基本的に桁数は固定します．
桁数を固定すると扱える数字に制限がかかりはしますが，実装が楽になります．
最近のコンピュータのOSは64bitのことが多いですね．
64bitで扱える自然数は$0 \sim 2^{64}-1 = 18446744073709551615$です．
しかし，普通は負の数も扱えた方が便利なので，$-2^{63} \sim 2^{63} - 1$の範囲の整数を扱います．
負の数の扱いについては下の補数と減法のところで書きたいと思います．
2進数の小数も当然あって，固定点小数と不動点小数というものがあるのですが，
ちょっと長くなるので今回は省略します．

2進数の加減乗除

さて，2進数についてだいぶ分かってきたところで，2進数同士の加減乗除について考えていきましょう．

加法

まず加法，つまり足し算ですが，これは筆算ができます．
10進数の19，2進数で10011と10進数の22，すなわち2進数で10110を筆算で足してみましょう．

  1   1 1
    1 0 0 1 1
+)  1 0 1 1 0
--------------
  1 0 1 0 0 1

2行目と3行目にそれぞれ桁をあわせて数字を書き，
各桁ごとに足し算をします．繰り上がりも適切に処理をします．
出てきた結果101001は10進数に直すと41で確かに19 + 22の答えと一致します．

2進数$a = (a_i)^n_{i=0}$と$b = (b_i)^m_{i=0}$の和
$a + b = s = (s_i)^l_{i=0}$の数式での表記は，繰り上げ用の$(c_i)^l_{i=1}$を用意して
（$a_i, b_i, c_i, s_i\in\{0, 1\},\ l = \max\{n, m\} + 1$¹⁰），

\begin{equation}
\begin{split}
s_i &= (a_i + b_i + c_i) \bmod 2\\
c_i &= \begin{cases}
0\quad&(a_{i-1} + b_{i-1} + c_{i-1} = 0, 1)\\
1\quad&(a_{i-1} + b_{i-1} + c_{i-1} = 2, 3)
\end{cases}
\end{split}\tag{$\dagger$}
\end{equation}

となります．¹¹

補数と減法

続いて引き算を考えましょう．
引き算も筆算ができるのですが，繰り下がりとかが結構面倒くさいです．
そこで，中学校で習った$a - b = a + (-b)$というのを思い出すと，
引き算は負の数の足し算で書くこともできるというのがありました．
これを利用しましょう．

さて，上で負の数を2進数で表す話をしましたが，
ここで負の数を2種類の4bitの2進数の記法で表してみたいと思います．
4bitなので10進法で$-8 \sim 7$の数字を表すことができます．

10進数	2進数 表記1	2進数 表記2
7	0111	0111
6	0110	0110
5	0101	0101
4	0100	0100
3	0011	0011
2	0010	0010
1	0001	0001
0	0000 (1000)	0000
-1	1001	1111
-2	1010	1110
-3	1011	1101
-4	1100	1100
-5	1101	1011
-6	1110	1010
-7	1111	1001
-8	----	1000

表記1も2も0以上の数の表記は同じなのですが，
負の数の表記は表記1の方が1番上のbitに1を立てて，下3bitは正の数と同じ表記になっています．
一方表記2の方は一見するとどういうルールで割り当てられているのか分かりづらいですね．
実は実際によく使われているのは表記2の方で，2の補数と言います．
なぜこちらの方がよく使われているかは，引き算をしてみると納得できます．
例えば$6 - 3$，すなわち$6 + (-3)$をやってみましょう．

  1 1
    0 1 1 0
+)  1 1 0 1
------------
  1 0 0 1 1

10011となりましたが，4bitなので最上位bitの結果は捨てます．
すると0011となり，正しい計算結果である10進数の3を返してくれます．
疑り深い方のために$-6 + 1$をしてみると，

    1 0 1 0
+)  0 0 0 1
------------
    1 0 1 1

と1011という結果が出ますが，これを表記2の列から探すと正しく-5と計算できています．

正の2進数$a = (a_i)_{i=0}^{n-1}$の2の補数$b = (b_i)_{i=0}^{n-1}$を求める方法は，
$a + b = 0$となることが必要条件なので，式($\dagger$)を用いて，

\begin{align*}
a_i + b_i + c_i = 0\hspace{50pt}\\
c_i = \begin{cases}
0\quad&(a_{i-1} + b_{i-1} + c_{i-1} = 0, 1)\\
1\quad&(a_{i-1} + b_{i-1} + c_{i-1} = 2, 3)
\end{cases}\tag{$\ddagger$}
\end{align*}

となります．
これだと少し分かりづらいですが，もう少し分かりやすいアルゴリズムがあって，

1. 元の数の各桁の0と1を反転させる．
2. できた数に1を足す．

というものです．数式で上の$a, b$に加えて$d = (d_i)_{i=1}^{n-1}$を用いて，

\begin{align*}
d_i &= 1 - a_i\\
b &= d + 1
\end{align*}

となります．
これがうまくいっていることを4bit2進数の5を変換してみて確認しましょう．

\begin{align*}
a &= 0101\\
d &= 1010\\
b &= 1011
\end{align*}

となって確かに上の補数表で-5に相当する1011になっていることが分かります．
実際，式($\ddagger$)とこのアルゴリズムが等価であることを確認するのは簡単で，
$a + d$がすべてのbitが1になるので，
$a + b = a + d + 1$は$n + 1$bitの最上位bitが1で，それ以下のbitはすべて0になるので，
最上位bitを捨てれば確かに$a + b = 0$となることが分かります．

ここで$b$の補数を$b'$としたとき，$a - b = a + b'$となることを示さなければ
ならないのですが，すみません．書きかけです．

乗除法

すみません，この節は書きかけです．

書いてみての感想

常識的なことしか書くつもりないし，楽勝っしょって思ってたら，
意外と書かないといけないことがたくさんあって，めっちゃ疲れました……
ここら辺の理論は情報系と数学系のどちらかに偏った本ばっかりしか見たことがないので，
バランス良く書けてたら良いなと思っています．
（と思って見直したら，ほとんど数学っぽいことしかしてないなあ．
はやく論理回路部分に行きたい．目指せ全加算回路．）
感想，誤りの指摘，その他お待ちしてます．

次回はかの有名な@groebner_basisさんです！

脚注

1. なぜC++かというと，実家近くの県立図書館にC++の本しかなかったから． ↩

2. 論理回路はデジタル回路とよぶこともある． ↩

3. $\{0, 1\}$で要素が0と1からなる集合を表します．集合論は数学の言語とも言うべき理論です． ↩

4. #0は自然数! ↩

5. 一応$a_{m-1}\neq 0$という条件がつきます．数学的には端から無限桁の表記を考える方が自然で，そうすればこの条件は要りません． ↩

6. 厳密には$a\in\mathbb{N}$と$(a_j)\in\bigcup_m S^m$の間に全単射があることを示さなければいけません． ↩

7. 数学では$(a_0, a_1, a_2, a_3) = (1, 1, 0, 1)$と書くことが多いですが，分かりやすさを優先してこういう表記にしました． ↩

8. 学校で$x^0 = 1, (x\neq 0)$と教わりましたね． ↩

9. $a \bmod b$は$a$を$b$で割った余りのことです．a % bと同じですね． ↩

10. $\max\{a, b\}$とは，$a$と$b$のうち「値の小さくない方」を返す関数です． ↩

11. $c_i$の式がいまいち美しくないので，もう少し良い書き方があるかもしれない． ↩