#add two binary from back to front, I think it is very self explained, when 1+1 we need a carry.
class Solution:
def addBinary(self, a, b):
if len(a)==0: return b
if len(b)==0: return a
if a[1] == '1' and b[1] == '1':
return self.addBinary(self.addBinary(a[0:1],b[0:1]),'1')+'0'
if a[1] == '0' and b[1] == '0':
return self.addBinary(a[0:1],b[0:1])+'0'
else:
return self.addBinary(a[0:1],b[0:1])+'1'
An accepted concise Python recursive solution 10 lines


I used Python with bitwise solution. It can be found on cc150.
The solution does not calculate carry digit by digit but use and("&") operator, which means, if two digits are "1", there must be a carry equals 1. But we need to left shift("<<") it because the carry is one digit higher.
for the part not include carry, we can use XOR(^), 1^1 = 0, 1 + 1 = 10, without carry ,it is also "0".class Solution: # @param a, a string # @param b, a string # @return a string def addBinary(self, a, b): if a == "": return b if b == "": return a a_2 = int(a,2) b_2 = int(b,2) carry = 1 while carry != 0: carry = (a_2 & b_2)<<1 a_2 = a_2 ^ b_2 b_2 = carry return bin(a_2)[2:]

Thank you for your sharing! I think it can be more concise like the following (Actually, it's really an awesome answer! ):
class Solution: def addBinary(self, a, b): if len(a)==0: return b if len(b)==0: return a if a[1] == '1' and b[1] == '1': return self.addBinary(self.addBinary(a[0:1], b[0:1]), '1') + '0' else: return self.addBinary(a[0:1], b[0:1]) + str(int(a[1]) + int(b[1]))

@MengJu I agree that the solution can be narrowed down to only three if statements, but I feel it would be better to take advantage of the fact that we can use bitwise operations:
if len(a) == 0: return b if len(b) == 0: return a if int(a[1]) & int(b[1]): return self.addBinary(self.addBinary(a[0:1], b[0:1]), str(int(a[1]) & int(b[1]))) + str(int(a[1]) ^ int(b[1])) else: return self.addBinary(a[0:1], b[0:1]) + str(int(a[1]) ^ int(b[1]))

@wenchao_hu
it is coolat first, i use .repalce('0b', '') instead of [2:], it only beats 10%, i beat 75% when i use the latter..
