#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