概要
コンピュータ内での演算の基本は論理演算です。
論理演算ができる電子回路(論理回路)があれば、 加減乗除などの算術演算も実現可能です。
ということで、ここでは、論理回路の話を少しつまむ程度に話をしておきます。 例として、加算器の作り方や、負の数の表現方法を説明します。
論理演算
「n 進数」で、 コンピュータの中では 0, 1 の2進で数値を表しているという説明をしました。
0, 1 は電圧の高低で表されているわけで、high / low と言ってもいいし、 on / off と言ってもいい。 0 が偽(false)で 1 が真(true)を表していると考えて、 真偽値(boolean)とか論理値(logical value)とか言ったりもします。
で、2進数の 0, 1 を false / true の真偽値だとみなしていろいろ演算することを、 論理演算(logical operation)とかブール演算(boolean operation)といいます。 (ちなみに、ブール(George Boole)は人名。論理演算を考えた人。)
論理演算というと、分かりやすいのは AND, OR, NOT の3つです。 それぞれ、「a かつ b」、「a または b」、「a の逆」です(表1)。
AND | OR | NOT | ||
日本語名称 | 論理積 | 論理和 | 否定 | |
論理演算子 | a ∧ b | a ∨ b | ¬ a | |
代数的記法 | ab | a + b | ||
読み方 | a かつ b | a または b | a の否定、非 a | |
a | b | a ∧ b | a ∨ b | ¬ a |
---|---|---|---|---|
0 | 0 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 0 |
その他、NAND, NOR, XOR, XNOR (EQ) なんてものもあります。 NAND, NOR は NOT AND, NOT OR の略で、 名前どおり、AND と OR を否定したもの。 XOR は a と b が違うとき真、 XNOR (EQ) は a と b が同じとき真になる2項演算です(表2)。
NAND | NOR | XOR | XNOR (EQ) | ||
日本語名称 | 否定論理積 | 否定論理和 | 排他的論理和 | XOR の否定(等価) | |
論理演算子 | ¬ ( a ∧ b ) | ¬ ( a ∨ b ) | a ⊕ b | a ≡ b | |
代数的記法 | + a b | + ab | |||
a | b | ¬ ( a ∧ b ) | ¬ ( a ∨ b ) | a ⊕ b | a ≡ b |
---|---|---|---|---|---|
0 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 0 | 0 | 1 |
表2の「代数的記法」の行のように、NAND, NOR, XOR, EQ は、 AND, OR, NOT を使って表すことができます。 さらに言うと、AND と NOT があれば OR も作れます。 あと、a NAND a が NOT a と同じになるので、 NAND 1個だけでも他の演算を全部表現できます。
NAND 演算を電子回路を使って実現するのは(少なくともトランジスタの動作が分かれば)割りと簡単で、 よくある実現方法として CMOS NAND 回路というのがあります。 ここではあまり詳しくは触れませんが、興味があればこの単語をキーワードに検索してみてください。
加算器
前節の最後でちょこっとだけ触れましたが、 論理演算は電子回路を用いて簡単に実現できます。 (これを論理回路と呼びます。)
では、2進数の算術演算(加減乗除とか)はどうでしょうか。 実は、算術演算も、論理演算を使って実現することができます。 ということで、ここでは、例として加算器の作り方を説明します。
まあ、まずは1桁だけの場合を考えて見ましょう。 a も b も1ビット(1桁)の論理値として、 (論理和ではなくて)数値としての和 a + b を求めることを考えます。 (なお、本節では、 算術和と論理和の区別のために、論理積/和は a ∧ b , a ∨ b で書き表します。)
1桁同士の足し算なので、結果は2桁(以下)になるはずです。 足し算結果を表にすると、表3のようになります。
a | b | a + b |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 10 |
これを、1桁目の足し算結果 s と、2桁目への繰り上がり c に分けて書くと、 表4のようになります。
a | b | c | s |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 |
1 | 0 | 0 | 1 |
1 | 1 | 1 | 0 |
前節の表と見比べてみると、 c = a ∧ b , s = a ⊕ b になっていることが分かります。
それでは、桁数を増やしてみましょう。 数値 a, b の 2進数 n 桁目のビットをそれぞれ an, bn で表してみます。 1ビット目と違って、下の桁からの繰り上がり cn も考えて、 n ビット目の足し算結果 sn 上の桁への繰り上がり c n +1 は表5のようになります。
an | bn | cn | c n +1 | sn |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 0 |
1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 1 |
だいぶ複雑に見えますが、 論理回路に関して勉強すれば、 この表を論理演算で表現する方法も分かります。 (詳しくは「論理回路」あたりをキーワードに検索を。)
とりあえずここでは、算術演算も論理演算の組み合わせで実現できるということを示したいだけなので、 結論だけ書きますが、 c n +1 、 sn は以下のような論理式で表されます。
ちなみに、 c n +1 は、 a, b, c の3個中2個以上が 1 のときに結果が 1 になるので、 多数決回路と呼ばれています。 また、 sn の方は、 1 の数が奇数個のときに結果が 1 になっています。
この式が分かれば加算器を作るのは簡単で、 この論理式を a, b の桁数分並べれば OK。 ( そういう単純な方式の加算器を桁上げ伝搬加算器(ripple carry adder、ripple は波紋の意味)と呼びます。 あんまり動作は高速じゃなくて、 実際は何桁か先の繰り上がりを別に計算する桁上げ先見加算器なんてものも考えられていて、 こちらの方が賢い実装方法です。 )
ということで、少し飛ばし飛ばしの説明でしたが、 要するに、 「論理演算ができる回路があれば、算術演算も回路化できる」、 「コンピュータ内の演算の基本は論理回路」というのがポイントです。
負の数
次は、負の数の表現の仕方を考えてみます。 符号と絶対値を別々に持つとか、いろいろ考えられるんですけども、 よく使われるのは「2の補数表現」と呼ばれる表現方法です。
2の補数は、 a に対して、各ビットを 0, 1 反転させた上で1を足すことで作ります。 例えば、4ビット(2進数4桁)で表される数値の場合、 2の補数は表6のようになります。
a | −a | |
---|---|---|
10進数 | 2進数 | |
0 | 0000 | 0000 |
1 | 0001 | 1111 |
2 | 0010 | 1110 |
3 | 0011 | 1101 |
4 | 0100 | 1100 |
5 | 0101 | 1011 |
6 | 0110 | 1010 |
7 | 0111 | 1001 |
要するに、n ビットの2進数 a に対して、 a + b =2n になる数 b が a の2の補数です。
4ビットの例、すなわち表6の例では、 表の2列目と3列目の2進数を足すと、どの行も 10000 になります。 これを4ビット+4ビット → 4ビットの演算と考えるなら、 5ビット目の1は無視されて(というか、わざと無視して) 0 になるというわけです。
「負の数」 = 「足して 0 になる数」ということで、 この2の補数を負の数の表現として使うといろいろと都合がいい。 具体的には、 正の数同士の加算器とかをそのまま使って正負問わず整数の加算・減算ができるようになります。 あと、最上位の1ビットを見れば符号が分かる(0 なら正、1 なら負)というのも利点。
ちなみに、2の補数という言葉は、 「足して 2 n になる数」 という意味なので、本当は 2 n の補数という方がいいのかもしれない。 まあ、習慣的に2の補数と呼びます。
ただし、2の補数表現では、 2 n −1 の扱い (4ビットの場合は 8)にだけは気をつけないといけません。 8 は2進数で書くと 1000 なわけですが、 これの2の補数は 1000 で元のままです。 最上位ビットが 1 なので、2の補数表現としてはこれは -8 とみなすべきなんですが、 要するに、+8 は4ビットでは表現できないし、 -8 は -1 をかけたつもりでも -8 のままになってしまいます。
ちなみに、あんまり使われることはないんですが、 符号絶対値表現とか、1の補数表現なんてものもあるので、 参考程度に表7にまとめておきます。
a | −a | |||
---|---|---|---|---|
10進数 | 2進数 | 符号絶対値表現 | 1の補数 | 2の補数 |
最上位1ビットだけ 0, 1 反転 | 全ビット 0, 1 反転 | 1の補数 + 1 | ||
0 | 0000 | 1000 | 1111 | 0000 |
1 | 0001 | 1001 | 1110 | 1111 |
2 | 0010 | 1010 | 1101 | 1110 |
3 | 0011 | 1011 | 1100 | 1101 |
4 | 0100 | 1100 | 1011 | 1100 |
5 | 0101 | 1101 | 1010 | 1011 |
6 | 0110 | 1110 | 1001 | 1010 |
7 | 0111 | 1111 | 1000 | 1001 |