#-*- coding:utf-8 -*-
'''
Exercises 2.1-4：
Consider the problem of adding two n-bit binary integers,
stored in two n-element arrays A and B. The sum of the two
integers should be stored in binary form in an (n + 1)-element
array C. State the problem formally and write pseudocode for
adding the two integers.
算法思想：
我们可以将两个数组看做是两个逻辑运算单元的寄存器。
寄存器中的数相加的时候需要一个寄存器保存进位，实际
中相加的数有三个，即两个数组中的数和进位寄存器中的
进位。相加结果如果大于1，则必须进位，即进位寄存器
里的数要加1。
'''
def sum_binary(A, B, n):
count = 0
C = [0] * (n + 1)
for i in range (n - 1, -1, -1):
C[i + 1] = A[i] + B[i] + count
if C[i + 1] <= 1:
count = 0
elif C[i + 1] == 2 :
C[i + 1] = 0
count = 1
elif C[i + 1] ==3 :
C[i + 1] =1
count = 1
#C数组的第一位存入最后一步运算得到的进位值
C[0] = count
return C
a = [1, 0, 0, 1, 1, 1]
b = [0, 1, 1, 1, 0, 1]
print u'A数组保存的二进制数是:',a
print u'B数组保存的二进制数是:',b
print u'数组二进制数之和为:', sum_binary(a, b, len(a))
