while循环将执行多少次？

Z时代
2024-01-10
分类：问答

我想知道这个while循环" title="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。

让我们看一下不同的情况，

同时出现A = B = 0。
在这种情况下，循环迭代= 0为的次数B = 0。

何时A != 0和B = 0。
在这种情况下，循环的迭代次数也= 0为B = 0。

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

如果A = B和A != 0和B != 0。
在这种情况下，次数的循环迭代= 2，因为在第一次迭代的价值A = 0，为什么？因为bitwise XOR两个相同的数字总是0和价值Y =
B，因为bitwise AND两个相同的数字是数字本身，然后B = Y << 1，在第一次迭代之后，A = 0 并B !=
0因此这case变成。因此，迭代次数将始终为2。

如果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。