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

无进位加法器的算法：

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 = 0B

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

如何制定更快的算法？ 我们来看看不同的案例，

• 情况 1：当两者都A = B = 0.
  在本例中，循环迭代的次数= 0为B = 0。
• 情况 2：当A != 0和 时B = 0。
  在这种情况下，循环迭代的次数也= 0为B = 0。
• 情况 3：当A = 0和 时B != 0。
  在本例中，循环迭代的次数是因为在第一次迭代之后，当您对结果执行任何二进制数的as 时= 1， as 的值就是数字本身。因为任何数字的值为。所以，你可以看到then和。X = Bbitwise XOR0Y = 0bitwise AND00Y = 0B = 0Y << 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。

源代码请参阅无进位加法器解决方案。

PS 对于无进位加法器的平均情况分析，可以参考论文：无进位加法器的平均情况分析：平均log(n) + O(1)步骤加法：简单分析。