无进位加法器算法

代码语言：javascript复制function no_carry_adder(A,B)

while B != 0:

X = A XOR B, Bitwise-XOR of A,B.

Y = A AND B, Bitwise-AND of A,B.

A = X

B = Y << 1, Multiplying Y by 2.

return A正如您所看到的，while循环一次又一次地执行这四个指令，直到B = 0，当B = 0时，存储在A中的二进制数字就是答案。现在的问题是找出while循环在B = 0或B变为零之前执行多少次。

如果我采用了一种天真的方式，即按照任何编程语言所描述的那样编写算法，就会给我一个答案，但如果二进制字符串A和B中的位数是> 500，则会很费时。

，我怎样才能做一个更快的算法？，让我们来看看不同的情况，

案例1:时两个A = B = 0。

在这种情况下，循环将= 0作为B = 0迭代的次数。案例2: When A != 0和B = 0.

在这种情况下，循环将= 0作为B = 0迭代的次数也是如此。案例3: When A = 0和B != 0.

在本例中，循环迭代= 1的次数是因为在第一次迭代之后，X = B的值与使用0处理任何二进制数的bitwise XOR一样，结果是数字本身。Y = 0的值，因为带有0的任意数字的bitwise AND是0。所以，您可以看到Y = 0，然后是B = 0和Y << 1 = 0。案例4: When A = B和A != 0和B != 0。

在这种情况下，循环迭代= 2的次数是因为在第一次迭代中A = 0的值，为什么两个相同数字的bitwise XOR总是0，而Y = B的值是两个相同数字的bitwise AND本身是数字，然后是B = Y << 1，在第一次迭代之后，A = 0和B != 0使得这个情况变成e 163 case -3E 264。因此，迭代的次数总是2。案例-5： When A != B和A != 0和B != 0.

在这种情况下，循环迭代= length of the longest carry-chain的次数。计算最长进位链长度的算法：

首先，如果二进制字符串A和B不相同，则使它们具有相同的长度。由于我们知道最大进位序列的长度将是答案，我只需要找到我已经出现的最大进位序列长度。所以，为了计算这个，我将从左到右迭代，即LSB到MSB，并且：代码语言：javascript复制- `if carry + A[i] + B[i] == 2` means that bit marks the start of carry-sequence, so `++curr_carry_sequence` and `carry = 1`.

- `if carry + A[i] + B[i] == 3` means the carry which was forwarded by previous bit addition is consumed here and this bit will generate a new carry so, length of carry-sequence will reset to 1 i.e. `curr_carry_sequence = 1` and `carry = 1`.

- `if carry + A[i] + B[i] == 1 or 0` means carry generated by the previous bit resolves here and it will mark the end of the carry-sequence, so the length of the carry-sequence will reset to 0. i.e. `curr_carry_sequence = 0` and `carry = 0`.​

现在，如果curr_carry_seq长度是>而不是max_carry_sequence，那么就更新max_carry_sequence。答案是max_carry_sequence + 1。有关源代码，请参阅无进位加法解。

关于无进位加法器的平均情况分析，请参阅论文：平均步骤:一个简单的分析。