高校情報I 半加算器—和と桁上がりを別の出力として回路から組み立てる｜武蔵野個別指導塾

2入力の全組を表にし、和の桁と桁上がりの信号を算術の結果につなぐ半加算器を考えます。

よくあるのは、2つの入力が両方1のときも、足した結果を1桁の1で答えてしまう場面です。1と1を足すと個数は2になりますが、1桁で表せる状態は0と1です。そこで、下の桁の値と、上の桁へ渡す値を別々に記録します。

何を入力し、何を答えるか

半加算器は、0か1の2つの入力 A、B を足して、下の桁 S と桁上がり C を出す回路です。ここでの和 S は結果全体ではなく、結果の下の1桁を指します。出力を並べて書くときは、上の桁を先にして C、S の順とします。たとえば C が1、S が0なら、2桁の「10」です。これは十進数の十ではなく、2の位が1、1の位が0なので、個数としては2です。

問われ方には、入力から出力を求める型、真理値表から回路を選ぶ型、回路の誤りを入力例で見つける型があります。どの型でも、まず2つの出力を別々の列にします。その後、各行で C が表す2個と S が表す1個を合わせ、入力した個数に戻るか調べます。出力の並び順が逆になると同じ2つの信号でも値が変わるため、表の見出しも確認します。

入力は各1ビットで、前の桁からの桁上がりは入力しません。0と1以外はこの回路の入力条件の外です。ここでは2入力の加算に限り、それより多い入力を足す回路や部品の物理的な仕組みには進みません。

信号の役割を分ける

ANDは両方が1のときに1、それ以外は0を出します。XORは排他的論理和と呼び、2つの入力が異なるときに1、同じときに0を出します。ORは少なくとも一方が1なら1なので、両方が1の行でXORと異なります。この行が2つの演算を見分ける重要な境目です。

図1のように、同じ A と B を2つの演算に渡し、XORの出力を S、ANDの出力を C とします。枝分かれした線は同じ入力値を伝えるもので、足し算を2回行うという意味ではありません。S と C は別の場所へ出る信号です。

入力が00なら足す個数は0、出力は C、S が00です。01と10なら個数は1なので01です。11なら個数は2で、1の位に0を置き2の位に1を立てるため10です。下の桁が1になるのは入力が異なる2行、上の桁が1になるのは両方1の行です。それぞれXORとANDの条件に一致します。

全4行を列挙できるのは、それぞれの入力が0か1のどちらかだからです。どの行でも、C を2個分、S を1個分と数えると A と B の個数の合計に戻ります。これはこの入力範囲での成立理由です。数例の実行結果だけを根拠にするのではなく、取りうる組を漏れなく調べています。

基本例題: 2つの状態を足す

2つの装置の状態 A、B を、それぞれ停止なら0、作動なら1で表します。両方が作動中のとき、作動中の装置の数を半加算器で表してください。答えは C、S の順に2桁で書きます。装置の状態は入力条件を満たすものとします。

まず A は1、B も1です。手で数えると作動中は2台です。XORには同じ値が2つ入るので S は0、ANDには1が2つ入るので C は1です。よって C、S は10です。2の位の1が2台、1の位の0が0台を表し、手で数えた2台に戻ります。図2のように途中の判定を分けると、出力の役割を混ぜずに済みます。

次の自作プログラムは、同じ2つの値から2出力を作ります。入力はコード中の整数で、表示は C、S を空白で区切った2個の整数です。

a = 1
b = 1
s = int(a != b)
c = int(a == 1 and b == 1)
print(c, s)

1行目と2行目は2台の状態をそれぞれ変数に置きます。3行目の不一致の判定は、両方1なので偽です。intによって偽を0にして S に置きます。4行目は両方が1かを判定し、真を1にして C に置きます。最後に上の桁を先に表示します。期待出力は 1 0 です。Python 3.14.8で実行した出力も 1 0 でした。実行した値を台数の意味へ戻し、2台と一致するところまで確認します。

全組を比べて設計を確かめる

標準例題として、2つのランプの点灯状態を入力にし、消灯を0、点灯を1とします。入力全組について、出力を C、S の順に2個の整数で出してください。期待する順序は00、01、10、11の順です。1行に A、B、C、S を空白区切りで並べます。

手計算では、点灯数が0、1、1、2となるため、出力は順に00、01、01、10です。入力が入れ替わった01と10では点灯数が同じになり、出力も同じになるはずです。11では2個を表す上の桁が必要です。

for a in (0, 1):
    for b in (0, 1):
        s = int(a != b)
        c = int(a == 1 and b == 1)
        print(a, b, c, s)

外側の反復は A を0、1の順に選びます。内側はその各値について B を0、1の順に選びます。内側の反復が終わると次の A に進み、どちらも有限個の値を使い終えると止まります。3行目と4行目でその組の S と C を作り、5行目で入力と出力を並べます。Python 3.14.8での期待出力と実際の出力は次のとおりです。

0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

各行をランプの個数に戻すと0、1、1、2です。表の4組に重なりや欠けはありません。たとえば最後の 1 0 を出力全体で1個と数えるのではなく、左側の桁に2個分の重みを与えます。

条件の外にある値を分ける

発展例題です。状態を記録する処理で、2入力のうち片方に整数2が渡されました。0か1の整数以外は計算せず、文字列 error を返す仕様にします。正常な入力なら C、S の順の組を返します。整数の0と1に限定し、真偽値や文字列の 1 も受け付けません。外の道具から得た値が壊れている場合も、この境界で拒否します。通信の時間切れや外部装置の故障そのものはこの関数の入力ではなく、呼び出し側が値を渡す前に扱います。

def half(a, b):
    if type(a) is not int or type(b) is not int:
        return "error"
    if a not in (0, 1) or b not in (0, 1):
        return "error"
    s = int(a != b)
    c = int(a == 1 and b == 1)
    return (c, s)

for pair in ((0, 0), (1, 1), (2, 1), ("1", 0)):
    print(half(pair[0], pair[1]))

1行目は2値を受け取る関数を定義します。2行目は両方が整数かを調べ、違えば3行目で終了します。4行目は整数でも0か1でない値を除き、5行目で終了します。6、7行目は条件を通過した値だけから信号を作り、8行目で C、S の組を返します。最後の2行は4組を順に渡し、返り値を表示します。添字0が最初の値、1が次の値です。4組を使い終えれば反復は終了します。

Python 3.14.8での期待値と実際の出力は次のとおりです。

(0, 0)
(1, 0)
error
error

最初の2行は0個と2個に戻ります。後の2行は入力条件外なので、誤った個数として扱われていません。たとえば2をそのまま不一致の判定に入れると、信号らしい0や1が出ても、本来の入力条件を満たすことにはなりません。条件外を拒む検査と、条件内で回路が正しいことの検査は別の役割です。

誤答をたどって直す

和 S をORで作る誤りを考えます。01ではORもXORも1なので、この1行だけでは誤りが現れません。11を入れるとORは1、ANDも1です。C、S を11とすると、2個分と1個分で3個を表し、入力の2個と一致しません。図3のように食い違いは S の判定で初めて生じます。

誤った式は s = int(a == 1 or b == 1) です。原因は「少なくとも片方」と「ちょうど片方」を同じ条件と考えたことです。s = int(a != b) に修正し、11を再実行すると C、S は10になります。さらに00、01、10でも前の真理値表と照合します。誤りを見つけた行だけを直後に試すと、その修正が他の行を壊したかは判定できないからです。

出力の順序を逆にする別の誤りもあります。01で S、C をそのまま書くと10になり、1個の入力を2個と読んでしまいます。演算が正しくても、列の名前と並び順の確認が必要です。値を覚える前に、それぞれの桁の重みへ戻して点検します。

入力と出力の対応を表にするときは、入力列を先に固定してから出力列を埋めます。行を順に並べれば、同じ入力を2度数える誤りや、11の行を落とす誤りに気づきやすくなります。回路の線を追う際も、各入力から2つの演算へ同じ値が届くことを確認します。途中で片方の値を変えてしまうと、表は元の入力の加算を表しません。

練習: 状態と回路を行き来する

各問で入力は0か1です。出力は指定の形で答え、個数に戻して確認してください。

1. 2枚の札の表を1、裏を0とします。1枚目が裏、2枚目が表のとき、表の枚数を C、S の順の2桁で答えてください。
2. 2つの扉の開きを1、閉じを0とします。両方閉じているときの C と S を、順に2個の整数で答えてください。
3. 2個のボタンが両方押されている状態を1、1とします。S をOR、C をANDにした誤回路の出力を C、S の順に2桁で答え、正しい個数との差を整数で答えてください。
4. 入力 P、Q が1、0のとき、S をXOR、C をANDで求めます。出力を C、S の順に2桁で答え、PとQを入れ替えた場合の出力も答えてください。
5. 2つのセンサーの状態を0か1で表します。出力が C、S の順で01のとき、入力の組を P、Q の順にすべて挙げてください。組は (P, Q) の形で書きます。

解答と照合

1. 入力は0、1です。異なるので S は1、両方1ではないので C は0です。答えは01です。1の位の1は表の札1枚に戻ります。
2. 入力は0、0です。同じなので S は0、両方1ではないので C も0です。答えは 0 0 です。どちらの桁も0なので開いた扉は0個です。
3. ORもANDも1なので誤出力は11です。これは3個を表しますが、押されたボタンは2個です。差は1個です。正しい S は入力が同じため0で、正しい出力10は2個へ戻ります。
4. 不一致なので S は1、両方1ではないので C は0です。答えは01です。入れ替えた0、1でも01です。どちらも1個を表し、入力の1の個数と一致します。
5. 答えは (0, 1) と (1, 0) です。00は出力00、11は出力10なので該当しません。2組とも入力中の1は1個で、出力01の1個と一致します。

練習の検算では、上の全組を出すプログラムの表から各入力の行を読み、別に個数を数えました。問3の誤回路は11に対してORとANDをそれぞれ手で評価し、問5は4行を逆向きに調べました。全組の実行結果に加え、表の各行を元の札、扉、ボタン、入力の個数へ戻して答えの形を確認しています。

覚えておくこと

• S はXOR、C はANDで求めます。
• C、S の順では左が2個分、右が1個分です。
• 11の入力で出力は10になり、ORとの違いが現れます。
• 入力の条件と出力の順序を先に決めます。

詰まった場所を言葉にする

個別指導で確かめるなら、まず11を見せ、1が2つあることと出力の10を自分の言葉で結べるかを見ます。次に表の S の列と C の列を隠して順に埋め、どちらの条件を使ったか説明します。01と11を比べてORとXORが分かれる行を探せれば、式の取り違えを自分で発見できます。

出力は合っていても理由があいまいなら、C を2個分として数え直します。入力が条件外のときに表を使ってよいかも確認し、計算の前提と結果の検証を分けます。2つの出力の意味を結び直せば、1桁に収まらない和も読める半加算器です。