全加算器

Python

京子ちゃんは 二進数 の整数同士で足し算をするプログラムを作成したいと思っています。
二進数の足し算において、下から 1 けた目の計算は半加算器でできることを知り、 2 けた目の計算も同じように足し算ができないかと考えています。



上記の画像のように、 現在下から 2, 3 けた目を計算しようとしています。そこで、入力 A, B と 1 けた目からの繰り上がり C1 が与えられます。 京子ちゃんに変わって C2 と S を計算し、出力してください。

この問題は少し難しいので、ヒントとなる画像を用意しました。 2 つの半加算器と XOR 演算を用いることで計算することができます。

 

#入力

A B C1

 

 

#出力

C2, S をこの順に、半角スペース区切りで出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。

C2 S

 

 

#コード

a,b,c = map(int,input().split())

cx = (a & b)
sy = (a ^ b)

cy = (sy & c)
s = (sy ^ c)
c2 = *1


print(c2,s)

 

 

#参考

    • まず、 問題文に記載されている全加算器の回路図に記載されている、半加算器の出力に名前をつけましょう。下図の左の半加算器の出力を Cx, Sy 、右の半加算器の出力を Cy, S としました。

  • 半加算器は 2 度計算する必要があるので、関数としてまとめるとプログラムの見栄えが良くなります。
  • ヒントがなかった場合、本問題は本当に難しいのでしょうか。そのようなことはありません。順を追って考えてみましょう。まず、 S は A, B, C1 の和です。 A + B + C1 = (A + B) + C1 であるので、 S は半加算器を 2 つ用いれば計算できます。
  • 次に C2 に関して考えてみます。 C2 が １ になりそうな条件を列挙しましょう。
    1. A + B で繰り上がりが発生した場合
    2. (A + B)の 1 けた目 + C1 で繰り上がりが発生した場合
    3. (A + B) , (A + B)の 1 けた目 + C1 の両方で繰り上がりが発生した場合
  • 1 、 2 に関しては正しいです。しかし、 3 に関してはあり得ません。 A + B で繰り上がりが発生した場合、 A + B の 1 けた目は 0 であるため、 C1 が何であろうと (A + B)の 1 けた目 + C1 で繰り上がることはありません。
  • よって A + B 、 (A + B)の 1 けた目 + C1 のどちらか片方の半加算器の結果 C が 1 になった場合、 C2 を 1 にすればよいです。これは XOR 演算または OR 演算で実現可能です。

実装例

a, b, c1 = map(int, input().split())

# 半加算器のプログラム
def halfAdder(a, b):
    c = a & b
    s = a ^ b
    return (c, s)

cx, sy = halfAdder(a, b)
cy, s = halfAdder(sy, c1)
c2 = cx ^ cy

print(c2, s)
  • まず 1 行目で a, b, c1 を標準入力から受け取ります。
  • 次に半加算器の関数 halfAdder を作成します。 Python では値を 2 つ返す関数を作成することができます。
  • あとは上記の全加算器の図のように半加算器を 2 回計算し、 cx と cy の XOR 演算を計算すれば、答えを得ることができます。

*1:cx ^ cy) | (cx | cy