使用进位的二进制加法

Question

我尝试使用递归将两个二进制数 S 和 T 转换为以 10 为底的数字，但我很难将进位合并到代码中。另外，如果一个二进制数比另一个长，我不确定该怎么办。

def addB(S,T):
  '''adds binary number without converting to base 10'''
  def addBhelper(S,T,carry):
    if S=='' and T=='':
        return ''
    if S[-1] + T[-1]+carry==0:
        return addBhelper(S[:-1],T[:-1],0) + str((carry+int(S[-1]) + int(T[-1]))% 2)
    if S[-1] + T[-1]+carry==1:
        return addBhelper(S[:-1],T[:-1],1) + str((carry+int(S[-1]) + int(T[-1])) % 2)
    if S[-1] + T[-1]+carry==2:
        return addBhelper(S[:-1],T[:-1],2) + str((carry+int(S[-1]) + int(T[-1])) % 2)
    if S[-1] + T[-1]+carry==3:
        return addBhelper(S[:-1],T[:-1],2) + str((carry+int(S[-1]) + int(T[-1])) % 2)
  return addBhelper(S,T,0)

---- 已更新以修复代码格式

Answer 1

让我们从第一部分开始，确保两个字符串的长度相同。因为它们是数字，所以你所要做的就是用“0”填充较短的数字

max_len = max(len(S), len(T))
# the more simple to understand way
while len(S) < max_len: S = '0' + S
while len(T) < max_len: T = '0' + T
# or you can use this python trickery
S = ('0' * (max_len - len(S))) + S
T = ('0' * (max_len - len(T))) + T

对于carry，你的carry应该是这样的：

For sum = 0, carry = 0
For sum = 1, carry = 0
For sum = 2, carry = 1
For sum = 3, carry = 1

希望对您有所帮助，

Answer 2

这是一个使用一些 Python 语法糖的更清晰的版本：

def add(a,b,c=0):
    if a == '' and b == '':
        return str(c)
    a = a or '0'
    b = b or '0'
    n = int(a[-1]) + int(b[-1]) + c
    return add(a[:-1],b[:-1],n//2) + str(n%2)

使用进位的默认值c=0去掉内部函数
a = a or '0' 将 a 设置为 '0' 如果它是 ''
您忘记在添加之前将字符串转换为整数
n//2 得到进位

使用进位的二进制加法

Binary Addition using a carry

python

binary

addition