jmcnuggsmagic13 jmcnuggsmagic13 - 1 month ago 44
Python Question

How to carry a digit when doing binary addition?

Code:

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'


So I have to make this function that takes two binary numbers and adds them. This has to be done using recursion and cannot convert the numbers to decimal, add and then convert back to binary. So my base cases say that if one binary number is empty return the other and vice a versa. Then for my recursive call if two zeroes are added it returns 0 and the recursive call. If a 0 and a 1 are added it adds one and a recursive call.

Now here's where I'm stuck. Two ones makes 0 and then you have to carry a 1 to the next side but I can't figure out how to do this within the second recursive call. Sum rest is the normal recursive call, then follows the recursive call to carry the digit, and then the 0. The function must stay as designed but the recursive call needs to be fixed.

Answer

Your overflow recursions must sum up '1' against sum_rest, not b2[:-1]. Overflow is carried over to the higher-valued digits.

Here's a slightly shorter implementation:

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'

For example, consider the binaries '011' and 110. You'd do the following operations by hand:

  • 0 + 1 => 1, keep 1, no overflow
  • 1 + 1 => 10, keep 0, overflow
  • 0 + 1 + 1 => 10, keep 0, overflow
  • / + / + 1 => 1, keep 1, no overflow
Comments