while循环将执行多少次？

无进位加法器 算法：

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

存储的二进制数

才是答案时。现在的问题是找出

while

循环将在零之前执行多少次

B = 0

或

变为零。

如果我已经为用简单的方式，因为它是任何编程语言来描述，即写算法喜欢它会给我一个答案，但它会很耗时，如果位的二进制串的数量

和

为

> 500

。

如何制定更快的算法？ 让我们看一下不同的情况，

情况1： 同时出现
```
A = B = 0
```
。
在这种情况下，循环迭代
```
= 0
```
为的次数
```
B = 0
```
。
情况2： 何时
```
A != 0
```
和
```
B = 0
```
。
在这种情况下，循环的迭代次数也
```
= 0
```
为
```
B = 0
```
。
情况3： 何时
```
A = 0
```
和
```
B != 0
```
。
在这种情况下，循环迭代的次数是
```
= 1
```
因为在第一次迭代之后，对结果进行任何二进制数运算的
```
X =B
```
as的值就是数字本身。因为与的任何数字的值是。所以，你可以看到，然后和。
```
bitwise XOR``0``Y = 0``bitwiseAND``0``0``Y = 0``B = 0``Y << 1 = 0
```
案例4： 如果
```
A = B
```
和
```
A != 0
```
和
```
B != 0
```
。
在这种情况下，次数的循环迭代
```
= 2
```
，因为在第一次迭代的价值
```
A = 0
```
，为什么？因为
```
bitwise XOR
```
两个相同的数字总是
```
0
```
和价值
```
Y =B
```
，因为
```
bitwise AND
```
两个相同的数字是数字本身，然后
```
B = Y << 1
```
，在第一次迭代之后，
```
A = 0
```
并
```
B !=0
```
因此这case变成 Case-3 。因此，迭代次数将始终为
```
2
```
。
案例5： 如果
```
A != B
```
和
```
A != 0
```
和
```
B != 0
```
。
在这种情况下，循环迭代的次数
```
= length of the longest carry-chain
```
。

计算最长进位链长度的算法：

首先，使二进制字符串
```
A
```
和
```
B
```
长度相等的二进制字符串（如果不相等）。
我们知道最大的进位序列长度就是答案，我只需要找到到目前为止一直发生的最大的进位序列长度即可。因此，要进行计算
我将从左到右进行迭代，即从LSB到MSB，然后：
- ```
if carry + A[i] + B[i] == 2
```
  表示该位标志着进位序列的开始，所以
```
++curr_carry_sequence
```
  和
```
carry = 1
```
  。
- ```
if carry + A[i] + B[i] == 3
```
  意味着在这里消耗了通过先前的位加法转发的进位，并且该位将产生一个新的进位，因此，进位序列的长度将重置为1即
```
curr_carry_sequence = 1
```
  和
```
carry = 1
```
  。
- ```
if carry + A[i] + B[i] == 1 or 0
```
  装置承载由前一比特做出决议产生这里它将标志着搬入序列的末尾，所以进位序列的长度将重置为0，即
```
curr_carry_sequence = 0
```
  和
```
carry = 0
```
  。
- 现在，如果
```
curr_carry_seq
```
  长度
```
>
```
  小于
```
max_carry_sequence
```
  ，则更新
```
max_carry_sequence
```
  。
答案是
```
max_carry_sequence + 1
```
。

有关源代码，请参阅No Carry Adder Solution。

PS有关 No-Carry Adder的 平均情况分析，请参阅以下文章：No Carry Adder的平均情况分析：

log(n) +O(1)

按平均步长进行加法：简单分析。

while循环将执行多少次？

面试问答相关栏目本月热门文章