无进位加法的复杂性
两个二进制数可以用通常的“常规、冗余”表示法表示（即引入另一个数字，例如 2，以获得非唯一的表示法，使得任何两个连续的 2 之间都有一个零），因此加法变成进位自由的。我听说复杂度是 O(k)，其中 k 是两个数字中较短的一个的长度。但算法本身是什么？它似乎没有出现在网络上的任何地方。我知道你可以在恒定时间内将 1 加到这样的表示中，以便结果保持规律性。但我不知道如何概括这一点。
Two binary numbers can be represented in the usual "regular, redundant" representation (i.e. introduce another digit, say 2, to obtain a non-unique representation such that any two consecutive 2's have a zero in between), so that addition becomes carry-free. I have heard that the complexity is O(k), where k is the length of the shorter of the two numbers. But what is the algorithm itself? It doesn't seem to appear on the web anywhere. I know you can add 1 to such a representation in constant time so that the result maintains regularity. But I don't know how to generalize this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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} 的特殊注意事项，它们在上述链接的电路图中定义。
I see this is an old post, and the poster does not have much recent activity here but thought I'd put forward the answer anyway.
In order to represent this circuit as a traditional equation, let's set forth some notation. Each 'bit' in RBR notation actually consists of two bits, so to refer to these right and left bits, I will use [0] and [1] respectively. To refer to a certain 'bit' position I will use braces {0},{1},{2},...{n}.
Addition of two or three single bits can result in a two-bit sum (the MSB is traditionally called the carry bit). These can also be referenced by [0] and [1], the latter being the carry bit. For example:
(0+1+1)[0]=0, (0+1+1)[1]=1, (0+0+1)[0]=1, (0+0+1)[1]=0Now without much further, the general algorithm for adding numbers z = x + y is given by:
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]You will note that there is some carrying going on here, but the algorithm achieves O(n) because the carrying is limited to two orders. Also note the special considerations for z{0} and z{1}, which are defined in the circuit diagram in the aforementioned link.