在这种情况下,您不需要递归。 让我们从最简单的实现开始:
- 实现一个全加器,它将在位上操作。
- 使用全加器实现一个涟漪加法器,它将在2个位列表上操作。
全加器的实现很直接。
def full_adder(a,b,cin):
sum_ = a^(b^cin)
cout = (a&b) | (a|b)&cin
return sum_, cout
测试以确保全加器符合规格:
>>> zero_one = (0,1)
>>> [full_adder(*x) for x in [(a,b,c) for a in zero_one for b in zero_one for c in zero_one]]
[(0, 0), (1, 0), (1, 0), (0, 1), (1, 0), (0, 1), (0, 1), (1, 1)]
由于涟波加法器的参数是列表,因此在进行加法运算之前,我们需要确保列表长度匹配。这可以通过在较短的列表前面填充零来实现。
def ripple_adder(xs,ys):
x, y = map(len, (xs, ys))
alen = max(x, y)
ax, by = map(lambda f: f if len(f) == alen else [0]*(alen-len(f)) + f, (xs, ys))
cout = 0
res = [0]*(alen)
for i in range(alen-1, -1, -1):
a, b, cin = ax[i], by[i], cout
s, cout = full_adder(a, b, cin)
res[i] = s
if cout:
res = [1] + res
return res
最后,我们通过涟漪加法器定义
bin_inc
二进制增量函数。
def bin_inc(bin_lst):
return ripple_adder(bin_lst, [1])
>>> bin_inc([1,1,1])
[1, 0, 0, 0]
>>> bin_inc([1,0,0,1])
[1, 0, 1, 0]
现在我们提供一个更简单但需要一点点见识的解决方案。考虑以下输入xs
和输出ys
的观察结果:
如果xs
全部为1,则ys
的长度将为L+1
,ys
的第一个元素将为1
,其余元素将为零。
如果xs
有一个零元素,让p
成为xs
中最后一个零元素的索引。
然后ys
将是由xs的前p
个元素组成的列表,后跟一个长度为L-p
的1和0。也就是说
ys = xs[:p] + [1] + [0]*(L-p)
。
我们可以很容易地将其转换为Python代码。我们使用Python的list.index
方法通过对列表进行反转来查找零的最后出现位置,并相应地调整算法:
def bin_inc_2(xs):
if all(xs):
return [1] + [0]*len(xs)
p = xs[::-1].index(0)
return xs[:-p-1] + [1] + [0]*p
这个实现方式比基于ripple_adder的实现更简单有效。你可能会注意到一个小缺点是,当xs有一个零元素时,我们需要遍历它来检查它是否全为1,然后再遍历一次以找到第一个零出现的位置。
我们可以通过使用一个try except块来简化实现并同时使其更符合Python语言风格:
def bin_inc_3(bin_lst):
try:
p = bin_lst[::-1].index(0)
return bin_lst[:-p-1] + [1] + [0]*p
except ValueError:
return [1] + [0]*len(bin_lst)
这个实现在源代码和Python语言方面都非常简单。现在我们将对其进行测试,以确保它能够与基于ripple_adder的加法器良好地配合使用。
>>> z_n = (0,1)
>>> xs = [[a,b,c,d,e,f,g,h] for a in z_n for b in z_n for c in z_n for d in z_n
for e in z_n for f in z_n for g in z_n for h in z_n ]
>>> print(all(ripple_adder(x, [1]) == bin_inc_3(x) for x in xs))
True
太棒了,它按预期工作,并通过测试正确处理前导零(测试将每个数字从0
增加到255
)。