#Rules of the game: Do not use python built-in integer arithmetic 
#We consider numbers as bit strings, and assume them to be non-negative



def Intify(L):    # This converts a bit string into a Python integer  
    s = 0         # We use this for checking correctness of our algorithms
    M = 1
    
    for j in L:
        if (j != 0):
            s = s+ M
        M = M*2 
    return s

                    
def Add(L1,L2):		# Adds two numbers
    
    if (len(L1) <  len(L2)):
        L1, L2 = L2, L1  #swaps the pointers to the two lists     
            
    Out = []
    carry = 0

    for i in range(len(L1)):
        if (i < len(L2)):
            h = carry + L1[i] + L2[i]
        else:
            h = carry + L1[i]
        
        Out.append(h%2)
        
        if h > 1:
            carry = 1
        else:
            carry = 0                     
    
    if carry == 1:
        Out.append(1)
    return Out 


def Sub(L1,L2): # Computes L1-L2. Error if result is negative.

    i = len(L1)
    while (i<len(L2)): # completes L1 with 0s if L2 is longer
      L1.append(0)
      i=i+1
      
    Out = []
    carry = 0

    for i in range(len(L1)):
        if (i < len(L2)):
            h = L1[i] - L2[i] - carry
        else:
            h = L1[i] - carry
        
        Out.append(h%2)
        
        if h < 0:
            carry = 1
        else:
            carry = 0                     
    
    if carry == 1:
        return -1 # if the last carry is 1, L2 was bigger than L1. The algorithm reports an error
    return Out 


def Leading1(L):
    s = -1
    for i in range(len(L)):
        if L[i] != 0:
            s = i
    return s


def Multiply(L1,L2):    # Simple Multiplication
    if Leading1(L2) == -1:    #check L2 does not represent 0
        return [0]
    else:
        H =list(L2)
        b = H.pop(0)
        Z = Multiply(L1,H)
        Z.insert(0,0)
        if b == 0:
            return Z
        else:
            return Add(Z,L1)
        
    
#Tests    

L1 = [1, 1,1,1,0,1]

print L1 , Intify(L1), "\n"

L2 = [1,0,1,1]

print L2 , Intify(L2), "\n"

L3 = Add(L1,L2)

print "Sum" , L3 , Intify(L3), "\n"

L4 = Sub(L1,L2)

print "Substraction" , L4 , Intify(L4), "\n"

L5 = Multiply(L1,L2)

print "Product" , L5 , Intify(L5), "\n"