MathString

## # Solution

Let $m$ be the length of a and $n$ be the length of b.

### # Convert to Int (trivial)

Use the built-in functions int to convert and format/f-strings (opens new window) to return a string.

Using format function:

def addBinary(self, a: str, b: str) -> str:
return '{0:b}'.format(int(a, 2) + int(b, 2))

1
2

Using f-strings:

def addBinary(self, a: str, b: str) -> str:
return f'{int(a,2)+int(b,2):b}'

1
2

### # RCA (Ripple Carry Adder)

Complexity

time: $O(\max(m, n))$
space: $O(\max(m, n))$

def addBinary(self, a: str, b: str) -> str:
n = max(len(a), len(b))
a, b = a.zfill(n), b.zfill(n)

carry = 0
for i in reversed(range(n)):
if a[i] == '1':
carry += 1
if b[i] == '1':
carry += 1

if carry % 2 == 1:
else:

carry //= 2

if carry == 1:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

### # Bit Manipulation

This solution requires previous knowledge, or supreme ingenuity.

Use x to store the sum (XOR of 2 binaries) and y to store the carry (AND of 2 binaries and left shifted by 1). Keep doing this until carry is 0.

Complexity

time: $O(\max(m, n))$
space: $O(\max(m, n))$

def addBinary(self, a: str, b: str) -> str:
x, y = int(a, 2), int(b, 2)
while y:
carry = (x & y) << 1
return bin(x)[2:]

1
2
3
4
5
6
7

An equivalent but even shorter solution is to replace the while loop content with:

x, y = x ^ y, (x & y) << 1

1