while循环将执行多少次？

问题内容：

我想知道这个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 
``

问题答案：

无进位加法器 算法：

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： 何时A != 0和B = 0。
在这种情况下，循环的迭代次数也= 0为B = 0。
情况3： 何时A = 0和B != 0。
在这种情况下，循环迭代的次数是= 1因为在第一次迭代之后，对结果进行任何二进制数运算的X = Bas的值就是数字本身。因为与的任何数字的值是。所以，你可以看到，然后和。bitwise XOR``0``Y = 0``bitwise AND``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循环将执行多少次？

微信关注