本シリーズは、論理回路で電卓を作ろうと思い、そのために勉強した結果を残しているものだ。
初回は、そもそも論理回路とは何だっけとなり、それをまとめた。
また、基本となるAND、OR、NOTの動作と、数式で表現する方法や回路を表現する手法の一つである論理回路図もまとめた。
今回はいきなり横道に逸れるが、これらは常に使うことになるので、しっかり身に付けておきたい。
以下がその記事だ。
さて、今回は2進数をやっていこう。
前回の中で、入力や出力それぞれは、YESかNOの2択になると書いたと思う。
この2択と、今回解説する2進数が密接に絡んでくる。
これが具体的に分かるのは後の方になると思うが…まあ、下準備と思って進めていこう。
2進数…の前に、進数って何？
まずはここから解説していこう。
進数とは、いくつの数を使って数字を表すか…という表現でいいのだろうか。
例えば、普段我々が使っている数字。
これは、0から9の10種類を使って表しているので、10進数というものになる。
他にも、時間を思い浮かべてみよう。
例えば、私が1記事を書き切るのは、スムーズにいけば大体2時間30分程度。
この時間は、分を基本的な単位としたとき、60分ごとに時の数字が一つ増えていく。
150分ではなく、2時間30分と表記するのが普通だろう。
分の単位に0から59の60種類を使っているので、60進数とみなすことができる。
…60時間を上の単位に上げることはないので、2桁限定だが。
こんな感じで、ある数字を表現する時に、何種類の表記を使うか、という考え方が進数となる。
2進数
では、この2進数を見ていこう。
なお、この2進数の2はもちろん10進数で表現している。
上の説明通りに考えると、2種類のみで数を表現する、となるが…まあ、その通りだ。
使うのは、0と1。
これだけで数が表現できるのかと言われると、どんな数でもできる。
先に進む前に、ここからは異なる進数の数がたびたび出現する。
明確に表記していれば分かるのだが…書き方を決めておこう。
n進数の数を書く時は、その数字自体を括弧で囲み、後ろに下添え字で進数であるnを表記することにする。
例えば、123が10進数で書かれていることを表す時は…
$$(123)_{10}$$
と書く、ということだ。
特に断りなく数字を書く場合はこの表記にするので、それで何進数の数かを見分けて欲しい。
また、これは別にこの記事特有というわけではなく、一般的に使われている記法なので、他の資料を参考にする際にも覚えておくといいだろう。
桁と2進数→10進数の変換
さて、通常使っている数…10進数の場合から見ていこう。
例えば、\((123)_{10}\)という数があるとする。
これは、100を1個、10を2個、1を3個と見ることができるだろう。
このように、1、2、3それぞれを桁と呼ぶ…のは大丈夫だと思う。
では、もうちょっと数学的に。
この各桁は、一番下を0桁目として、n桁目は\(10^n\)の個数と見ることができる。
\((123)_{10}\)なら…
$$1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0$$
とみなすことができるのだ。
念のため指数の補足だが、任意の自然数\(m\)について、\(m^0 = 1\)だったことを思い出そう。
では、ここで2進数について見てみる。
0と1しか使わないので、例えば2進数の数は\((1001)_2\)といった形になっている。
これでも、10進数と同じく桁を考えてみよう。
10進数では、各桁は\(10^n\)がいくつあるか、という考え方だった。
2進数ではどうなるか…想像付くと思う。
やはり一番下の桁を0番目として、n番目の桁は\(2^n\)の個数を表している。
つまり、\((1001)_2\)は…
$$(1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0)_{10}$$
となっている。
…何かお気づきかもしれない。
実は、これはそのまま2進数から10進数への変換方法になっているのだ。
では、実際に計算してみよう。
$$\begin{eqnarray}
& & (1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0)_{10} \\
& = & (1 \times 8 + 1 \times 1)_{10} \\
& = & (8 + 1)_{10} \\
& = & (9)_{10}
\end{eqnarray}$$
ということで、\((1001)_2 = (9)_{10}\)となった。
幾つか練習で、適当に0と1を並べ、それを10進数に直してみるといいだろう。
答え合わせは、ネットで調べれば2進数から10進数に直すサイトが出てくるので、それで確かめよう。
10進数→2進数の変換
では、今度は逆方向を考えてみよう。
論理回路で数字を計算するとき、やはり0or1で表現するので、2進数で計算できると嬉しい。
だが、いきなり2進数の数同士を計算したい…なんて場面はあんまりないだろう。
つまり、普段使っている10進数を2進数に変換する必要が出てくる。
ひとまず、手作業で行う方法を紹介しよう。
まずは愚直に考えてみる。
例えば、\((13)_{10}\)を2進数に直したい。
ということで、2進数に直した時に、各桁が0か1のどちらになるかを考えてみよう。
まず、\(2^4\)の桁。
これは\((16)_{10}\)で、\((13)_{10}\)はそれより小さいので0、これ以上の桁も全て0なので、\(2^3\)以下だけ考えればいい。
で、その\(2^3\)の桁は8がいくつあるかで、1個ありそうだ。
つまり…
$$(13)_{10} = (1 \times 2^3 + 5)_{10}$$
となり、あとはこの5の部分をなんとかしよう。
これを続けていくと…
$$\begin{eqnarray}
(13)_{10} & = & (1 \times 2^3 + 5)_{10} \\
& = & (1 \times 2^3 + 1 \times 2^2 + 1)_{10} \\
& = & (1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1)_{10} \\
& = & (1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0)_{10}
\end{eqnarray}$$
となった。
つまり、\((13)_{10} = (1101)_2\)、ということだ。
…が、毎回こんな計算をするのは面倒だろう。
そこで、簡単に10進数から2進数に変換するための考え方がある。
同じく、\((13)_{10}\)で考えてみよう。
まず、これを2で割り、商と余りを求める。
$$13 \div 2 = 6 … 1$$
なお、余りは3点で書くようにしてみた。
この商に対して同じように2で割り…というのを、商が0になるまで続けよう。
$$6 \div 2 = 3 … 0$$
$$3 \div 2 = 1 … 1$$
$$1 \div 2 = 0 … 1$$
ここまで。
さて、ではここまで出てきた余りを、出てきたのとは逆順に上の桁から並べてみよう。
そうすると…
$$(1101)_2$$
と、先ほど計算した通りになっている。
なぜこれでいいかの証明は省略するが…これが、10進数から2進数に変換する考え方だ。
これも、2進数から10進数と同じく、適当な数で練習してみるといいだろう。
計算
さて、ここまでで2進数とは何かが分かり、10進数との相互変換ができるようになった。
では、次にこの2進数同士で計算することを考えてみよう。
乗算、除算は難しいので、まずは加算と減算を。
…とはいっても、ほぼ10進数のままなのだが。
加算
具体例で計算してみよう。
\((101)_2\)と\((011)_2\)を足してみる。
まあ、10進数の時と同じ…なのだが、2になったら桁が上がることだけ注意だ。
\(2^0\)の位は1と1の足し算なので2になり、桁上がりが発生して0になる。
\(2^1\)の位は0と1の足し算、かつ下の位からの桁上がりがあるので、さらに桁上がりが発生して0。
\(2^2\)の位も同じく1と0の足し算と桁上がりがあり、ここでも桁上がりして0。
\(2^3\)の位は桁上がりだけ受けているので1。
ということで、\((101)_2 + (011)_2 = (1000)_2\)となった。
念のため、10進数に直して確認してみよう。
\((101)_2 = (5)_{10}\)、\((011)_2 = (3)_{10}\)で、\((5 + 3)_{10} = (8)_{10}\)。
\((1000)_2 = (8)_{10}\)なので、合っていることが分かると思う。
減算
次に減算、これも先ほどと同じ2つの2進数を使って、\((101)_2\)から\((011)_2\)を引いてみよう。
\(2^2\)の桁は1から0を引くので、そのまま1。
\(2^1\)の桁は0から1を引く、上から桁下がりしてきて、\(2^2\)の位が0になり、\(2^1\)の位は1。
\(2^0\)の桁は1から1を引いて、そのまま0。
ということで、\((101)_2 – (011)_2 = (010)_2\)となった。
\((010)_2 = (2)_{10}\)で、10進数でも明らかに\(5 – 3 = 2\)なので問題ないだろう。
桁の制限
さて、ここまでの例では、特に桁を制限せずに計算を行っていた。
だが、論理回路で表現しようとする場合には、桁数は限られてくる。
あらかじめ決めた桁数までしか計算ができないのだ。
ということで、2進数で書ける桁数が決まっている場合を考えてみよう。
例えば、4桁…つまり、最上位が\(2^3\)の位だったとする。
これで、\((0101)_2\)と\((1101)_2\)を足してみよう。
10進数だと、\((5)_{10}\)と\((13)_{10}\)なので、答えは\((18)_{10}\)となるはず…
ということで、2進数で計算すると、\((10010)_2\)となる。
…のだが、今は4桁と制限していたはずだ。
つまり、最上位の1は書くことができず、結果は\((0010)_2\)となる。
これは10進数で直すと\((2)_{10}\)だ。
桁数が制限されてしまうと、こんな具合に情報が落ちてしまい、正確な計算ができない場合がある。
…ここで、頭がいい人はこう考えたんじゃないかな。
これを意図的に起こして、上手く使えないだろうか、と。
そして、こんな考え方が出てきた。
負の数を、これを利用して表現しよう。
2進数における負数
さて、ここからは桁数が制限されているという前提のもと解説を行う。
具体例では、4桁にしておこう。
先ほど挙げた例、10進数で言えば\(5 + 13\)の計算なのだが、結果は\((2)_{10}\)となってしまった。
これを、\((5 – 3)_{10}\)の結果として表現するのはどうか。
何を言っているか分からないと思うが、落ち着いてついてきて欲しい。
今問題になっているのは、制限されている桁よりも結果が大きくなると、情報が抜け落ちて別の値になってしまうということ。
が、その情報が抜け落ちる条件は決まっている。
そこをあえて狙って起こし、それを利用して負の数を表現してしまおう、というのがここの考え方だ。
そうなると、負の数をどう決めるかが問題となってくる。
どう考えると辻褄が合うかというと、符号が異なり、絶対値が同じ2つの数を足すと、0になる。
これを上手く利用するのだ。
例えば、4桁の制限で\((3)_{10}\)を考えてみる。
これに何かを足して答えが0になればいい。
もちろん10進数で考えれば\((-3)_{10}\)を足せばいいので、この\((-3)_{10}\)を2進数の何に対応させるか、という話になる。
そこで出てくるのが、制限を超えた桁が無視される、という性質。
つまり、\((11)_2 + \mbox{何か} = (10000)_2\)となればよくて、この何かを2進数における\((-3)_{10}\)としよう、ということだ。
単純に式変形して\(\mbox{何か} = (10000)_2 – (11)_2\)。
これを計算すると、何かは\((1101)_2\)となる。
こう考えると、先ほどやった\((5 + 13)_{10}\)もしっくりくる。
これを2進数で計算すると、答えは\((2)_{10}\)となった。
で、\((1101)_2\)はマイナスを考えない場合は\((13)_{10}\)、マイナスを考える場合は\((-3)_{10}\)となっている。
つまり、マイナスで考えると、この計算は\((5)_{10} + (-3)_{10}\)で、綺麗に辻褄が合うのだ。
このように、(論理回路を含む)桁数が決まっている場合は、2進数の引き算を負数の足し算で考えることができる。
ちなみに(というか重要な用語だが)、この\((0011)_2\)(10進数でいう3)に対する\((1101)_2\)(10進数でいう-3)のような関係を、2の補数と呼ぶ。
2の補数の求め方
さて、これが分かったのはいいが、毎回マイナスの値を求めるのに引き算とかしなきゃいけないの？と思われるかもしれない。
それが、2進数の場合は簡単に求めることができる。
先にやり方を。
- 各桁の0と1を反転させる
- それに1を足す
これで終わりだ。
なぜこれでいいか、さっきの\((11)_2\)で考えてみよう。
桁の制限は4桁で、\((11)_2 + \mbox{何か} = (10000)_2\)となる何かを求めればよかった。
一個、さっきと同じ式変形をする。
$$\mbox{何か} = (10000)_2 – (11)_2$$
ここで、ちょっと工夫をしてみよう。
そのまま引くのではなく、一旦1だけ避けておいて、後で足すように考える。
加算は順番が変わっても結果に影響がないので、この操作をしても問題ない。
$$(10000)_2 – (11)_2 = (1111)_2 – (11)_2 + (1)_2$$
さて、これで各桁が全て1の数から元の数を引くことになるのだが…今は2進数だ。
各桁について、元が0なら結果は1になるし、元が1なら結果は0になり、桁下がりは絶対に発生しない。
つまり、これが各桁の0と1を入れ替えると同じ。
これで入れ替えると\((1100)_2\)となり、あとは1を足せばいいので、\((1101)_2\)が2の補数になる、ということだ。
これが分かると何が嬉しいかだが…論理回路で加算とは別に、減算を行うための部分を作らなくてもよくなる。
各桁を反転させるのはNOTを挟めばいいし、1を足す部分は加算が使いまわせる。
それで符号を反転させ、もう一度加算を使えばいいのだ。
実は、乗算や除算も同じく加算を使いまわせる。
そのため、電卓を作る際にも、実際に計算する部分は加算のみで十分だ。
乗算や除算は別にカウンタが必要になるのでまだ現段階では組めないが、これもいずれ本シリーズで扱うことになるだろう。
マイナスの数と、表現できる範囲
桁数が決まっている時、マイナスの数を表現できるのは分かった。
じゃあ、その数字だけ見てそれが正か負かどうやって見分けるかという問題が出てくる。
これは、その数字の最上位の桁が0か1かで分けよう。
最上位が0ならその数は正の数。
最上位が1ならその数は負の数。
例えば、桁数が4桁の場合、\((0111)_2\)が正の数の最大で、\((7)_{10}\)。
負の数の最小は\((1111)_2\)…と思うかもしれないが、これは\((-1)_{10}\)だ。
実際は\((1000)_2\)が最小となり、\((-8)_{10}\)が表現できる最小値となる。
\((8)_{10}\)じゃないのかと思うかもしれないが、そこはそういう決まりだと思ってもらえればいいだろう。
ということで、\(n\)桁の2進数で表現できる範囲は、\(2^{n-1}-1\)から\(-2^{n-1}\)までになる。
ちょっとオマケになるが、Javaのint型で表せる整数の範囲は、-2147483648から2147483647まで。
なぜこうなっているかというと、同じように考えると綺麗に辻褄が合う。
このint型は、32桁の2進数で表現されているのだ。
つまり…
$$\begin{eqnarray}
& & (0111 1111 1111 1111 1111 1111 1111 1111)_2 \\
& = & (2^{31} – 1)_{10} \\
& = & (2147483647)_{10}
\end{eqnarray}$$
$$\begin{eqnarray}
& & (1000 0000 0000 0000 0000 0000 0000 0000)_2 \\
& = & (-2^{31})_{10} \\
& = & (-2147483648)_{10}
\end{eqnarray}$$
となっているので、この範囲になる。
おわりに
今回は、2進数にフォーカスを当てて解説してきた。
演算も加算、減算の2つだけ紹介し、その減算で使える2の補数というものを使って負の数を表現する方法も扱った。
電卓を組む場合は、論理回路で2進数の数を扱う必要が出てくる。
表現できる桁が決まっているという制約はあるが、それを逆手に取ってうまい具合に負数を表現するのはシンプルにすごいなと思った(小並感)。
さて、乗算・除算が残っているが…本文にも書いた通り、別のカウンタというものが必要になるので、一旦飛ばしてしまおう。
やり方だけ言ってしまうと、乗算は同じ数を何回も足せばいい。
除算は引ける回数をカウントし、それを商として表示すればOKだ。
…まあ、実際には小数をどうするかという別の問題も出てくるのだが、そこまで実装するかはまだ迷っているので、もし実装するなら解説をしていこう。
では次回何をするかという話だが、前回の続きに進んでいく。
前回やったAND、OR、NOTが最も基本的な要素になるのだが、これ以外にも基本となる回路は存在する。
それらと、他にもこの論理演算の性質について見ていくつもりだ。
2021/11/18追記
次回の内容を更新した。
XOR、NAND、NORという3つの回路と、論理演算について。
これで最低限の準備が整うことになるだろう。
今後も常に使う内容になるので、是非身に付けておくといい。
オマケ：16進数
いや、オマケにするほど小さい内容でもないのだが。
今回は2進数メインで扱いたかったので、あえてオマケとして16進数に触れていこうと思う。
16進数も、やはり2進数や10進数と同じく、16種類を使って数を表す手法だ。
…が、数字は0から9の10種類しかない。
では、残り6種類には何を使うかというと、ローマ字のAからFを用いる。
1桁の16進数と10進数の対応を表にしてしまおう。
| 10進数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 16進数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 10進数 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 16進数 | 8 | 9 | A | B | C | D | E | F |
もちろん、2桁以上になった場合の考え方も10進数や2進数と同じ。
例えば\((2E)_{16}\)となった場合は、以下のように考える。
$$\begin{eqnarray}
(2E)_{16} & = & (2 \times 16^1 + 14 \times 16^0)_{10} \\
& = & (32 + 14)_{10} \\
& = & (46)_{10}
\end{eqnarray}$$
さて、なぜこれを紹介したかというと、2進数と非常に親和性が高いからだ。
10進数で考えると、16というのは\(2^4\)だ。
つまり、2進数の数を表す時に、4桁ごとに区切ってそれぞれを16進数に対応させることで、簡単に相互変換ができるのだ。
今後、論理回路を組む際にはこの変換を多用して数字を表現することになる。
そのため、先に知識としてだけでも持っておいてもらいたいと思って、今回紹介した。
実際に使うのはかなり先になりそうな気がしているが…よかったら変換の練習などをしておくといいかもしれない。
なお、16進数自体は身近な例だと、カラーコードに使われている。
カラーコードとは、色を赤、緑、青の3原色の強さによって表現する手法で、よくRGB値とか聞いたことがあるだろう。
これも、元の3色の強さをそれぞれ0から255の256通りで表現している。
この256通りというのは、ちょうど16進数2桁で表現できる範囲なのだ。
よく、カラーコードで#ff22ffとか見たことがあると思うが、これは16進数2桁ずつ、赤、緑、青の順で数値を指定したもの。
こんなところにも使われていたりするので、ちょっと気にしてみると面白いかもしれない。
コメント