algorithm - 无进位加法的复杂性

Question

两个二进制数可以用通常的“常规、冗余”表示形式表示（即引入另一个数字，比如 2，以获得非唯一表示，使得任何两个连续的 2 之间都有一个零），因此加法变为进位 -自由的。我听说复杂度是 O(k)，其中 k 是两个数字中较短者的长度。但是算法本身是什么？它似乎没有出现在任何地方的网络上。我知道您可以在恒定时间内将这种表示形式加 1，以使结果保持规律。但我不知道如何概括这一点。

Answer 1

我看到这是一个旧帖子，并且海报最近没有太多活动，但我想我还是会提出答案。

为了将该电路表示为传统方程，让我们提出一些符号。RBR 表示法中的每个“位”实际上由两个位组成，因此要引用这些右位和左位，我将分别使用 [0] 和 [1]。要引用某个“位”位置，我将使用大括号 {0}、{1}、{2}、...{n}。

两个或三个单个位的相加可以产生两位和（MSB 传统上称为进位位）。这些也可以由 [0] 和 [1] 引用，后者是进位位。例如：
(0+1+1)[0]=0, (0+1+1)[1]=1, (0+0+1)[0]=1, (0+0+1)[1]=0

现在不用多说，添加数字 z = x + y 的一般算法由下式给出：
z{n}[0] = ((x{n-1}[1] + x{n-1}[0] + y{n-1}[1])[0] + (y{n-1}[0]) + (x{n-2}[1] + x{n-2}[0] + y{n-2}[1])[1])[1]

z{n}[1] = ((x{n}[1] + x{n}[0] + y{n}[1])[0] + (y{n}[0]) + (x{n-1}[1] + x{n-1}[0] + y{n-1}[1])[1])[0]

你会注意到这里有一些进位，但是该算法实现了 O(n)，因为进位被限制为两个订单。另请注意 z{0} 和 z{1} 的特殊注意事项，它们在上述链接的电路图中定义。