CLRS Exercise 2.1.4

Consider the problem of adding two n$n$-bit binary integers, stored in two n$n$-element arrays A$A$ and B$B$. The sum of the two integers should be stored in binary form in an (n+1)$(n+1)$-element array C$C$. State the problem formally and write pseudocode for adding the two integers.

This is an inefficient python implementation of the problem.

def add(A,B):
    n = len(A)
    C = [0 for x in range(n+1)]
    carry = 0
    A.insert(0,0)
    B.insert(0,0)
    for i in range(n,-1,-1):
        z = A[i] + B[i] + carry
        if z == 0:
            C[i] = 0
        elif z == 1:
            C[i] = 1
        elif z == 2:
            C[i] = 0
            carry = 1
        elif z == 3:
            C[i] = 1
            carry = 1
        else:
            raise "Something went wrong"
    return C

add([1,1,1],[1,1,1])