Как переносить цифру при выполнении двоичного добавления?

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'  

Так что я должен сделать эту функцию, которая принимает два двоичных чисел и добавляет их. Это нужно сделать с помощью рекурсии и не может преобразовать числа в десятичные, добавить, а затем преобразовать обратно в двоичный. Поэтому в базовых случаях говорят, что если одно двоичное число пусто, верните другое и наоборот. Затем для моего рекурсивного вызова, если два нуля добавлены, он возвращает 0 и рекурсивный вызов. Если добавлены 0 и 1, он добавляет один и рекурсивный вызов.

Теперь вот где я застрял. Два из них делают 0, а затем вы должны переносить 1 на следующую сторону, но я не могу понять, как это сделать во втором рекурсивном вызове. Суммирующий остаток - это нормальный рекурсивный вызов, затем следует рекурсивный вызов для переноса цифры, а затем в 0. Функция должна оставаться такой же, как она была разработана, но рекурсивный вызов должен быть исправлен.

Answer 1

Ваши рекурсии переполнения должны подытоживать '1' против sum_rest, а не b2[:-1]. Переполнение переносится на более высокозначные цифры.

Вот несколько короче реализация:

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' 

Для примера рассмотрим двоичные файлы '011' и 110. Вы бы выполнить следующие операции вручную:

• 0 + 1 => 1, держать 1, нет переполнения
• 1 + 1 => 10, держать 0, переполнение
• 0 + 1 + 1 => 10, держать 0, переполнение
• / +/+ 1 => 1, держать 1, нет overflow