add_binary.py

#!/usr/bin/env python
'''
Leetcode: Add binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".
'''
from __future__ import division
import random

def valid_binary_str(s):
    for bit in list(s):
        if bit != '0' and bit != '1': return False
    return True

# Special cases: negative numbers? not a valid binary string?
def add_binary(a, b):
    if (not valid_binary_str(a)) or (not valid_binary_str(b)): return None
    
    print a,'+',b,'=',
    # make a and b of equal lengths
    l = max(len(a), len(b))
    while len(a) < l: a = '0'+a
    while len(b) < l: b = '0'+b
    
    i = l-1
    results = ""
    prev_carry = 0
    while i >= 0:
        x, y = int(a[i]), int(b[i])
        # add current bits
        z = x ^ y
        cur_carry = x & y
        # add previous carry
        if prev_carry == 1:
            if z == 1: z = 0; cur_carry = 1
            else: z = 1
        
        cur_carry = (z & prev_carry) | cur_carry
        z = z ^ prev_carry
        
        results = str(z) + results
        prev_carry = cur_carry
        i -= 1
    # last carry
    if prev_carry: results = '1'+results
    print results
    return results




if __name__ == '__main__':
    add_binary('11','1')
    add_binary('101011','1111')
    add_binary('101','1111')
    add_binary('0','0')
    add_binary('11','1222')