数えられない部品で計算する
自動販売機は、入れた100円玉と50円玉を一瞬で足して、150円と表示します。けれど、中のプロセッサの部品は、どれも数を数えられません。
1つ1つの部品は、2つのビットについて「はい」か「いいえ」を答えるだけです。今日は、その答えを組み合わせて足し算を作ります。
このレッスンのゴール
メモ
論理ゲートを組み合わせて、加算器を作ることができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 論理ゲート | 1つか2つの入力ビットから、1つの出力ビットを作る回路 | |
| 真理値表 | すべての入力と、そのときの出力を並べた表 | |
| 桁上がり | 和が大きすぎるとき、次のけたへ送る1ビット | キャリー |
| 半加算器 | 2つのビットを足す、ゲート2つの回路 | |
| 全加算器 | 2つのビットと桁上がりを足す回路 | |
| オーバーフロー | 答えが、決まったビット数に入りきらないこと |
学生が入力するセルは、このプレビューでは空白です。
4つのゲートが、ビットに答える
論理ゲートは、ビットを受け取って1ビットを返します。AND は、両方が1のときだけ1です。OR は、どちらかが1なら1です。XOR(排他的論理和)は、2つが違うときに1です。NOT は入力が1つで、それを反対にします。
真理値表は、すべての入力と出力を並べた表です。入力が2つなら場合は4つだけなので、表は短くなります。
真理値表: 3つのゲート
| A | B | A AND B | A OR B | A XOR B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
学生が入力するセルは、このプレビューでは空白です。
アーキテクチャのフォルダへ移る
cd ~/archここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
12 と 10 にゲートを当てる
python3 -c "print(12 & 10, 12 | 10, 12 ^ 10)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
例: ビットごとに見たゲート
| ビット | 10進数 | |
|---|---|---|
| A | 1100 | 12 |
| B | 1010 | 10 |
| A AND B | 1000 | 8 |
| A OR B | 1110 | 14 |
| A XOR B | 0110 | 6 |
学生が入力するセルは、このプレビューでは空白です。
ゲート2つで、2ビットを足す
2つのビットの足し算は、4通りです。0 + 0 は0、0 + 1 と 1 + 0 は1です。ところが 1 + 1 は2で、2進数では 10 と書きます。
答えの右のビットは A XOR B です。左のビット、つまり桁上がりは A AND B です。XOR ゲート1つと AND ゲート1つで、半加算器ができます。
真理値表: 半加算器
| A | B | 和(XOR) | 桁上がり(AND) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
学生が入力するセルは、このプレビューでは空白です。
XOR は、桁上がりを無視した和
python3 -c "print(12 + 10, 12 ^ 10, (12 & 10) << 1)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
全加算器は、桁上がりも受け取る
いちばん右以外のけたは、右のけたから来た桁上がりも足す必要があります。つまり、3つのビットを足します。
全加算器は、半加算器2つと OR ゲート1つでこれを行います。4つつなげば、4ビットの数を足せます。桁上がりは右から左へ、波が伝わるように順に送られます。そのため、これをリップルキャリー加算器と呼びます。
例: 0101 + 0011 を右から
| けた | A | B | 入る桁上がり | 和 | 出る桁上がり |
|---|---|---|---|---|---|
| 1の位 | 1 | 1 | 0 | 0 | 1 |
| 2の位 | 0 | 1 | 1 | 0 | 1 |
| 4の位 | 1 | 0 | 1 | 0 | 1 |
| 8の位 | 0 | 0 | 1 | 1 | 0 |
学生が入力するセルは、このプレビューでは空白です。
答えが入りきらないとき
加算器が残すビット数は決まっています。符号なしの数では、最上位から出た桁上がりは捨てられ、答えは0の側へ一周します。
符号付きの数では、見方が違います。0101 + 0011 は8ですが、4ビットの2の補数では 1000 は -8 と読まれます。正の数どうしを足して、負の答えになりました。最上位から何も出ていなくても、これもオーバーフローです。
180 と 90 を足すプログラムを書く
printf '.globl _start\n_start:\n li a0, 180\n li a1, 90\n add a0, a0, a1\n li a7, 93\n ecall\n' > wrap.sここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
アセンブルする
riscv64-linux-gnu-as wrap.s -o wrap.oここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
リンクする
riscv64-linux-gnu-ld wrap.o -o wrapここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
エミュレータで実行する
qemu-riscv64 ./wrapここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
終了ステータスを読む
echo $?ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
「オーバーフローとは、最上位から桁上がりが出ることだ」と考える人が多くいます。それは符号なしの数のときだけです。2の補数では、1110 + 0011 は桁上がりが出ますが、-2 + 3 = 1 で答えは正しいです。符号付きのオーバーフローは、同じ符号の2数を足して、答えの符号が変わったときに起きます。
さらに挑戦
プロセッサには、引き算専用の回路がありません。a - b を、a + (NOT b) + 1 として計算します。2の補数では、NOT b + 1 が -b になるからです。
課題の add_bits を使って subtract_bits(a, b) を書いてください。b の全ビットを反転して a に足し、さらに 0001 を足します。0110 - 0010 と 0010 - 0110 を試し、2回目の足し算を回路でどう省けるか考えましょう。