バイナリ追加の際に桁をどのように運ぶか？

Question

コード：

def add_bitwise(b1, b2): 
    '''Adds two binary numbers.''' 
    if b1 == '': 
     return b2 
    elif b2 == '': 
     return b1 
    else: 
     sum_rest = add_bitwise(b1[:-1],b2[:-1]) 
     if b1[-1] == '0' and b2[-1] == '0': 
      return sum_rest + '0' 
     elif b1[-1] == '1' and b2[-1] == '0': 
      return sum_rest + '1' 
     elif b1[-1] == '0' and b2[-1] == '1': 
      return sum_rest + '1' 
     elif b1[-1] == '1' and b2[-1] == '1': 
      return sum_rest + add_bitwise(b2[:-1],'1') + '0'  

だから私は2つの2進数を取り、それらを追加して、この機能を確認する必要があります。これは再帰を使用して行わなければならず、数値を10進数に変換したり、追加してからバイナリに変換したりすることはできません。だから、私の基本的なケースでは、あるバイナリの数字が空であれば、もう一方の数字を返し、逆もまた同様です。次に、2つのゼロが追加された場合の再帰呼び出しでは、0と再帰呼び出しが返されます。 0と1を追加すると、1と1が再帰呼び出しを追加します。

ここで私は立ち往生しています。 2つは0を作成し、次に1を次の側に持っていく必要がありますが、2回目の再帰呼び出しでこれを行う方法を理解できません。 Sum restは通常の再帰呼び出しであり、再帰呼び出しに続いて数字と0を続けます。関数は設計どおりの状態を維持する必要がありますが、再帰呼び出しを修正する必要があります。

Answer 1

オーバーフローの再帰は、とsum_restとの合計であり、b2[:-1]ではありません。オーバーフローは、より高い値の桁に引き継がれます。バイナリ'011'と110を検討し、例えば

def ab(b1, b2): 
    if not (b1 and b2): # b1 or b2 is empty 
     return b1 + b2 
    head = ab(b1[:-1], b2[:-1]) 
    if b1[-1] == '0': # 0+1 or 0+0 
     return head + b2[-1] 
    if b2[-1] == '0': # 1+0 
     return head + '1' 
    #  V NOTE V <<< push overflow 1 to head 
    return ab(head, '1') + '0' 

：

はここで少し短い実装です。いいえ、1を維持し、オーバーフロー

/ +/+ 1 => 1、

• 0 + 1 => 1 1、無オーバーフロー
• 1 + 1 => 10を維持し、0を維持し、オーバーフロー
• 0 + 1 + 1 => 10、0を保つ：あなたは手で次の操作を行いたいですオーバーフロー