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} 的特殊注意事项，它们在上述链接的电路图中定义。