while循环会执行多少次？

Question

我想知道这个 while 循环会执行多少次。这是一个使用 XOR 和 AND 将两个数字相加的函数。

def Add(x, y): 

    # Iterate till there is no carry  
    while (y != 0): 

        # carry now contains common 
        # set bits of x and y 
        carry = x & y 

        # Sum of bits of x and y where at 
        # least one of the bits is not set 
        x = x ^ y 

        # Carry is shifted by one so that    
        # adding it to x gives the required sum 
        y = carry << 1

    return x 
``

Answer 1

while循环执行多少次没有固定答案。当从一个位置到另一个位置有一个进位位时，总是执行 while 循环。因此，您需要知道这些数字在二进制中的样子。但是你可以肯定地说的是最大可能的执行次数是多少。它是较大数字的长度，如 bits + 1。为什么？因为如果那是进位可以最大发生的数量。让我们以 add(1,7) = 8 (001 + 111 = 1000) 为例。来自第一位的进位被传递到第二个位置，然后传递到第三个位置，然后传递到第四个位置。 4 次迭代，这相当于 7 的长度，即 + 1 = 4。

Answer 2

无进位加法器的算法：

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循环将这4条指令一次又一次地执行到B = 0，而当B = 0时，A中存储的二进制数就是回答。现在的问题是找出在 B = 0 或 B 变为零之前 while 循环将执行多少次。

如果我选择了天真的方式，即按照任何编程语言中描述的方式编写算法，它会给我一个答案，但如果二进制字符串中的位数 A 和 B 是 > 500。

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

情况一：当两个A = B = 0.
在这种情况下，循环迭代的次数 = 0 为 B = 0.
情况2：当A != 0和B = 0.
在这种情况下，循环迭代 = 0 的次数也是 B = 0。
情况三：当A = 0和B != 0.
在这种情况下，循环迭代的次数 = 1 因为在第一次迭代之后， X = B 的值与使用 0 对任何二进制数进行 bitwise XOR 时的值相同结果就是数字本身。 Y = 0的值是因为任何带0的数的bitwise AND都是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 所以这种情况变成 案例 3。因此，迭代次数将始终为 2。
Case-5: 当A != B and A != 0 and 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。

P.S。 No-Carry Adder的平均情况分析可以参考论文：Average Case Analysis of No Carry Adder: Addition in log(n) + O(1)Steps on Average: A Simple Analysis.

while循环会执行多少次？

How many times will the while loop be executed?

python

bit-manipulation

addition

bitwise-operators

time-complexity