たし算とひき算の回路 — 2進数加算器の仕組み

2. XORゲートの発見 — 半加算器

キャリービットの表はANDゲートで片づいたが、サムビットの表はどのゲートとも一致しない。ORの表とは1マスだけ、NANDの表とも1マスだけ違う——ならば同じ入力をORゲートとNANDゲートの両方に入れ、その2つの出力をANDゲートでまとめればよい。こうしてできる回路には名前がついている。排他的OR（XOR）ゲートである。どちらか一方だけが1のときに出力が1になるこの働きが、そのままサムビットの表になる。サムをXORで、キャリーをANDで出す小さなボックスが半加算器であり、前講で確立したリレーの数え方を使えば必要な個数まで数え上げられる。ただしこの部品には決定的な限界がある——「半」という名前が、その限界をそのまま言い当てている。

サムビットの表は、道具箱のどのゲートとも一致しない。しかし、惜しいものが2つある。 ORゲートの表は、両方の入力が1のところ（右下）だけが違う——ORは1を出すが、 サムビットは0でなければならない。NANDゲートの表は、両方の入力が0のところ（左上） だけが違う——NANDは1を出すが、サムビットは0でなければならない。どちらも1マスだけ外れている。

そこで、同じ入力AとBを、ORゲートとNANDゲートの両方に入れてみる。ORの出力が1に なるのは左上以外の3通り、NANDの出力が1になるのは右下以外の3通り。両方が同時に1になるのは、 その重なりである「どちらか一方だけが1」の2通りだけである。ということは、 2つの出力をANDゲートでまとめれば、欲しかったサムビットの表がそのまま得られる。

この回路——入力が2つ、出力が1つ——には名前がある。XORゲート （排他的OR、exclusive OR）である。「排他的」と呼ばれるのは、入力Aと入力Bの どちらか一方だけが1のときに出力が1になるからで、両方1のときは受け入れない。 記号はORによく似ているが、入力側にもう1本曲線が付く。XORは、この本で詳しく扱う最後の論理ゲート でもある。

この「OR＋NAND→AND」の組み立てを、実際に動かして確かめよう。入力A・Bを切り替えると、 ORとNANDそれぞれの出力、ANDでまとめた最終出力、真理値表の現在行が連動して変わる。 両方1にしたとき、ORは1のままなのにNANDが0に落ちて出力が0になる——「1マスだけ外れていた」 2つのゲートが互いの穴を塞ぐ様子を観察してほしい。

これで材料が揃った。サムビットはXORゲート、キャリービットはANDゲート。同じ入力A・Bを この2つのゲートに与え、出力をS（サムアウト）とCO（キャリーアウト）と名付けて1つのボックスに 収めたものを半加算器と呼ぶ。前講の数え方——ゲート1個はリレー2個——を使えば、 XORはOR・NAND・ANDの3個ぶんでリレー6個、半加算器はそれにキャリー用のANDを足してリレー8個で できていることになる。

ではなぜ「半」加算器なのか。2進数を筆算で足すとき、2桁目から先は「その桁の2つのビット」に 加えて「前の桁からの繰り上げ」も足し込む、3つの数の足し算になる。ところが半加算器の入力は 2つしかない。前の桁からのキャリービットを足し込めないため、この部品を使えるのは 繰り上げが来ない一番右の桁だけである——残り半分の仕事ができないから「半」なのである。なお電気工学 には、2つの入力が同じときだけ1を出す「一致ゲート」（XORの逆）が現れることもあるが、本講では扱わない。

このセクション: 0 / 5 問正解

3. 全加算器と8ビット加算器 — リプルキャリー

2桁目から先の足し算は、その桁の2つのビットに加えて前の桁からの繰り上げも足し込む、3つの数の足し算になる。半加算器2個とORゲート1個をつなぐと、この3入力の足し算をこなす全加算器ができる。2つの半加算器から出るキャリーアウトが同時に1になることは決してないため、まとめるのはXORではなくORで足りる——回路設計者の節約の知恵がここに現れる。全加算器を8個並べ、各桁のキャリーアウトを次の桁のキャリーインへ渡し、一番右の桁のキャリーインだけをグラウンド（=0）につなげば8ビット加算器の完成である。ただしこの構造には代償がある。各桁が前の桁の繰り上げを待つため、繰り上げが端から端へ波のように伝わる時間が、そのまま加算器の速度になる。

3つのビットを足すには、半加算器を2個とORゲートを1個つなぐ。1つ目の半加算器で入力Aと入力Bを足し、 そこから出たサムと、前の桁から来たキャリーインを、2つ目の半加算器で足す。2つ目の 半加算器から出たサムが、この桁の最終的なサムアウトである。

残るのは、2つの半加算器から1本ずつ出てくるキャリーアウトの扱いである。ここで「もう1個半加算器が 要るのでは」と思うかもしれない。それでももちろん動くが、入力の組み合わせをすべて調べると、 2つのキャリーアウトが同時に1になることは決してないとわかる。入力が同時に1に ならないのであれば、ORゲートはXORゲートとまったく同じ働きをする。だから、より少ないリレーで 済むORゲート1個でまとめれば足りる——回路設計者の節約の知恵である。

こうしてできたボックスが全加算器で、入力はA・B・CI（キャリーイン）の3つ、出力は S（サムアウト）とCO（キャリーアウト）の2つになる。たとえばA=1、B=1、CI=1を入れれば、1+1+1=3、 2進数では11——サムアウト1・キャリーアウト1である。

あとは全加算器を8個並べて配線するだけである。一番右の桁（1桁目）だけは事情が違う。この桁には 前の桁というものが存在しないので、繰り上げを受け取る相手がいない。0を入力する最も簡単な方法として、 1桁目のキャリーインはグラウンド（=0）につないでおく。2桁目から先は、前の桁の キャリーアウトをそのまま次の桁のキャリーインへ渡していき、最後の桁のキャリーアウトが9番目の電球に 流れ込む。これで8ビット加算器の完成である。

入力と出力のビットにはA0〜A7、B0〜B7、S0〜S7というラベルを付ける。下付き文字は0から始まり、 位が上がるほど大きくなる——ちょうど2の累乗の指数に対応している。右端が最下位ビット、 左端が最上位ビットである。この8ビット加算器をもう1個作ってカスケードにつなげば、 16ビットの数も足せるようになる。

ただし、この加算器には弱点がある。2桁目の計算は1桁目のキャリーアウトを、3桁目は2桁目のそれを 待たなければならない。繰り上げが右端から左端へ波（ripple）のように順に伝わっていくため、 加算器全体の速度はビット数×全加算器1個の速度になる。これを リプルキャリー（書籍表記では「リップルキャリー」）と呼び、高速化には ルックアヘッドキャリーという追加の回路が使われる。リレーの数はというと、 全加算器1個で18個、8ビット加算器で144個。もっとも現代のコンピュータはリレーではなく トランジスタを使っている——リレーと基本的に同じように機能しながら、ずっと速く、小さく、静かで、 消費電力が少なく、しかも安い。それでも必要な個数の考え方は変わらない。

図の左側にある半加算器を、実際に動かして確かめよう。A・Bを切り替えると、XORゲートが計算する サムビットSと、ANDゲートが計算するキャリービットCOが同時に更新される。1+1のときだけCOが1になり、 答えが「10」と2桁になる——全加算器8個を連ねる前に、この最小単位の動きを手で確認しておきたい。

このセクション: 0 / 5 問正解

4. 引き算のコツ — 補数で桁借りを追放する

「でも引き算はどうする？」——これは鋭い問いである。足し算は右端から左端へ一方向に進み、繰り上げを次の桁へ渡すだけで済むのに対し、引き算は上の桁から借りてくる「桁借り」が必要で、桁をまたいで行ったり来たりする別の仕組みになる。論理ゲートの一団にこのややこしい手順を教え込む代わりに、ここでは桁借りそのものを消してしまうコツを使う。10進数なら、減数を999から引いた9の補数を使う。この引き算はどの桁も9から引くだけなので、桁借りが起きようがない。2進数ではさらに簡単で、1の列から引くことは全ビットの反転にほかならない——前講で作ったインバータの再登場である。足し算と引き算を1つのスイッチで切り替える加減器では、XORゲートが「制御可能なインバータ」として働く。

リレーで加算器が作れると納得したところで、「でも引き算はどうする？」という疑問が湧く。これは 鋭いところを突いている。加算器は右端の桁から左端の桁へ一貫して進み、各桁の繰り上げを次の桁に 足すだけでよかった。ところが引き算では、繰り上げの代わりに桁借りをすることになる。 上の桁から借りて、借りた分を覚えておいて、と桁をまたいで行ったり来たりする——本質的に異なる、 煩雑な仕組みである。論理ゲートの一団をどう説得すれば、こんな手順を実行させられるだろうか。

答えは「させない」である。代わりに、ちょっとしたコツで桁借りそのものをなくしてしまう。 なお、引き算に使う2つの数には名前がある。被減数から減数を引き、 結果が差である。

3桁の10進数で考えよう。まず減数を、被減数からではなく999から引く。この結果を 9の補数と呼ぶ。どの桁も9から引くだけなので、減数が何であっても 桁借りは決して起きない。次にその9の補数を元の被減数に加え、最後に1を足して1000を引く。 これで元の引き算と同じ答えが出る。理屈は簡単で、元の式に1000を足して1000を引いても結果は 変わらないからである。

被減数 − 減数
= 被減数 − 減数 + 1000 − 1000
= 被減数 + (999 − 減数) + 1 − 1000

引き算1回を、引き算2回と足し算2回に置き換えた——一見損をしているようだが、その過程で いやな桁借りが全部消えている。そして2進数では、この技法はさらに簡単になる。減数を 1の列（11111111）から引いた結果を1の補数と呼ぶが、 1から0を引けば1、1から1を引けば0なのだから、これはすべてのビットを反転することと 同じである。実際に引き算をする必要はまったくない。前講で作ったインバータの 再登場である。

こうして8ビットの引き算の手順は、「減数の1の補数を作る → 被減数に加える → 1を加える → 256を引く」になる。最後の「256を引く」は、実回路ではもっと簡単になる。256は9ビット目の重みだから、 9ビット目のキャリーアウトを捨てるだけでよい——8ビットぶんしか配線のない回路では、 キャリーアウトを無視すれば自然にそうなる。ちなみに「1の補数を作って1を足す」をまとめた操作は、 次のセクションで見る2の補数そのものである。

ここまで来れば、加算器を改造して引き算もできる加減器にできる。足し算と引き算を 選ぶSUBスイッチを1つ足し、引き算のときだけ入力Bを反転すればよい。だが、 インバータを8個並べたのでは常に反転してしまい、足し算ができなくなる。そこで XORゲート8個を使う。「反転」というラベルの信号を各XORの片方の入力につないでおくと、 反転信号が0のときは入力がそのまま出て、1のときだけすべてのビットが反転する——XORが 制御可能なインバータとして働くのである。さらに引き算のときは加算器のキャリーインを 1にする。S3で「1桁目のキャリーインが空いている」と言ったのは、ここで「1を加える」ために使うから だった。

パネルの9番目の電球は、加減器では「Overflow/Underflow」ランプになる。SUB信号と加算器の キャリーアウトをXORに入れて点灯を制御する——足し算ではキャリーアウトが1なら255を超えた超過、 引き算ではキャリーアウトが0なら結果が負であることを意味するからである。ここで検出して いるのは、あくまで符号なしの計算の範囲超え（キャリー/ボロー）である。次のセクションで 扱う符号付き（2の補数）のオーバーフロー判定とは別物なので、混同しないでほしい。この機械は 負の数を表示するようには作られていない——「でも引き算はどうする？」は、やはりなかなか良い質問 だったのである。

このセクション: 0 / 5 問正解

5. 符号付き数 — 2の補数と符号ビット

負の数はどう表せばよいか。負の符号のためにビットを1つ立てる素朴な方法もそこそこうまくいくが、扱う数の範囲をあらかじめ決めてしまえば、もっと具合のよい体系が手に入る。10進数の10の補数に対応する2進数の体系が2の補数であり、その作り方は「全ビットを反転して1を足す」——1の補数に一手間を加えるだけである。8ビットなら表せる範囲は−128から+127までで、最上位ビットが符号ビットとして働く。この体系の美点は、足し算の規則だけで正の数と負の数を自由に足せることにある。範囲を超えたときの符号の化けを見抜く判定則と、その判定則が足し算限定であること、そして「同じビット列が−74にも182にもなる」という締めくくりが、第4講「ビットの正体」で見たテーマへ環を閉じる。

前のセクションでは負の数の話をしながら、負の数がどう見えるのかを示してこなかった。2進数でも 10進数と同じように負の符号を書く手もあるが、2進数を使う目的の1つは、どんな小さな記号でさえも 0と1で表すことにある。負の符号のためにビットを1つ用意し、1なら負・0なら正とする方法も そこそこうまくいく。だが、もっと具合のよい方法がある——面倒なことなしに、負の数と正の数を 足せる方法である。短所は1つだけ、扱う数の範囲をあらかじめ決めておかなければ ならないことだ。

考え方はこうである。ふだん私たちは、0を中心に正の数と負の数がどこまでも続いていくものだと 思っている。しかし「出てくる数はこの範囲に収まる」とわかっているなら、無限は要らない。範囲の 上半分を正の数に、下半分を負の数に割り当ててしまえば、負の符号を使わずに正負を書き分けられる。 10進数でこの割り当てをする体系を10の補数と呼び、数の並びは一種のサイクルになる （9の補数に1を足したものが10の補数である）。

2進数における対応物が2の補数である。作り方は前のセクションでほとんど出来上がって いる——全ビットを反転し（1の補数）、1を足す。それだけである。正から負へ変換する ときも、負から正へ戻すときも、同じ操作でよい。

+6 = 00000110
→ 反転 → 11111001（1の補数）
→ 1を足す → 11111010 = −6

8ビットで表せる256通りのパターンのうち、0で始まる128通りを0と正の数（0〜+127）に、1で始まる 128通りを負の数（−128〜−1）に割り当てる。したがって範囲は−128〜+127で、 最上位（左端）ビットが符号ビットとして働く——1なら負、0なら0か正である。

この体系の美点は、足し算の規則だけで正と負の数を自由に足せることにある。 引き算のために特別な回路を作らなくても、負の数を「足す」だけで済んでしまう。ただし1つだけ 例外がある。−128（10000000）は、反転して1を足しても10000000のまま自分自身に戻る。 +128は8ビットの範囲外で、対応する正の数が存在しないからである。範囲が−128〜+127と非対称なのは、 まさにこの理由による。

気をつけるべきはオーバーフロー／アンダーフロー——結果が範囲を超えると、符号が化ける。正の数 どうしを足したのに結果の符号ビットが1になっていたり、負の数どうしを足したのに0になっていたり する。そこで判定則はこうなる。2つのオペランドの符号ビットが同じなのに、結果の符号ビットが 異なるなら、その結果は無効である。符号の異なる2数の足し算は範囲を超えようがないので、 無効になることはない。

この判定則については、2つ注意がある。1つは、これが足し算のための規則だという こと。引き算を直接判定するには「被減数と減数の符号が異なり、かつ結果の符号が被減数と異なるなら オーバーフロー」という別の形を使う（たいていは「2の補数を足す」形に直して足し算の規則を当てれば よいが、減数が−128のときだけはその変換ができない——−128の2の補数は−128自身だからである）。 もう1つは、S4で見た加減器のOverflow/Underflowランプとは別物だということ。 あちらは符号なしの計算のキャリー／ボローを見ており、キャリーアウトだけでは符号付きの オーバーフローは判定できない。

最後に、この章の締めくくりにふさわしい問いを1つ。「8ビットの値10110110は、10進数でいくつか」。 正しい応答は「その数は符号付きか、符号なしか」と聞き返すことである。符号なしなら182、符号付き （2の補数）なら−74。数自体は、自分が符号付きか符号なしかを語らない。 第4講「ビットの正体」で見たとおり、ビットは単なる 0と1にすぎず、自分自身について何も語らない。同じ加算器が、解釈の取り決め1つで符号付きの計算まで こなしてしまう——ここでもそのテーマが顔を出した。次講では、この加算器とはまったく別の性質、 回路が「覚える」という不思議な働きに踏み込んでいく。

このセクション: 0 / 5 問正解