while循环将执行多少次？ [英] How many times will the while loop be executed?

问题描述

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

I am wondering about how many times this while loop would execute. This is a function that adds two numbers using XOR and 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 变为零。

As you can see, the while loop executes those four instructions again and again until B = 0, and when B = 0, binary number stored in A is the answer. Now the question was to find out how many times the while loop will execute before B = 0 or B becomes zero.

如果我只是天真的话，那就写算法，就像在任何编程语言中所描述的那样，它将给我一个答案，但是如果二进制字符串 A 和 B 中的位数为> 500 。

If I have gone for the naive way i.e write the algorithm as it is described in any programming language like it will give me an answer but it will be time-consuming if the number of bits in the binary string A and B is > 500.

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

How can I make a faster algorithm? Let's take a look at different cases,

• 情况1：当两个 A = B = 0 。
  
  在这种情况下，循环迭代 = 0 的次数为 B = 0 。


• 情况2：当 A！= 0 和 B = 0 。
  
  在这种情况下，循环还将 = 0 循环为 B = 0 。


• 情况3：当 A = 0 和 B！= 0 。
  
  在这种情况下，循环迭代 = 1 的次数，因为在第一次迭代之后， X = B ，就像对任何二进制数字 0 按位异或结果是数字本身。 Y = 0 的值是因为按位AND 任意数量的 0 为 0 。因此，您可以看到 Y = 0 ，然后 B = 0 和 Y<< 1 = 0 。


• 情况4：当 A = B 且 A！= 0 和 B！= 0 。
  
  在这种情况下，次循环迭代 = 2 ，因为在第一次迭代中， A = 0 的值，为什么是因为两个相同数字的按位XOR 始终为 0 且值 Y = B 按位AND 两个相同数字是数字本身，然后 B = Y<< 1 ，在第一次迭代后， A = 0 和 B！= 0 情况变为 Case-3 。因此，迭代次数将始终为 2 。


• 情况5：当 A！= B 和 A！= 0 和 B！= 0 。
  
  在这种情况下，循环迭代 =最长携带链的长度。

• Case 1: When both A = B = 0.
  In this case the number of times the loop iterates = 0 as B = 0.
• Case 2: When A != 0 and B = 0.
  In this case also the number of times the loop iterates = 0 as B = 0.
• Case 3: When A = 0 and B != 0.
  In this case, the number of times the loop iterates = 1 because after the first iteration, the value of X = B as when you do the bitwise XOR of any binary number with 0 the result is the number itself. The value of Y = 0 because bitwise AND of any number with 0 is 0. So, you can see Y = 0 then B = 0 and Y << 1 = 0.
• Case 4: When A = B and A != 0 and B != 0.
  In this case, the number of times the loop iterates = 2 because in first iteration the value of A = 0, why because bitwise XOR of two same numbers is always 0 and value of Y = B because bitwise AND of two same numbers is the number itself and then B = Y << 1, after the first iteration, A = 0 and B != 0 so this case becomes Case-3. So, the number of iteration will always be 2.
• Case-5: When A != B and A != 0 and B != 0.
  In this case, the number of times the loop iterates = length of the longest carry-chain.

计算最长携带链长度的算法：

• 首先将二进制字符串 A 和 B

• First make both the binary strings A and B of equal length if they are not.

我们知道最大进位序列的长度就是答案，我只需要找到最大进位序列的长度即可。到现在为止，我的序列长度已经发生。因此，为了进行计算，

As we know the length of the largest carry sequence will be the answer, I just need to find the maximum carry sequence length I have occurred till now. So, to compute that,

我将从左到右进行迭代，即LSB到MSB，然后：

I will iterate from left to right i.e. LSB to MSB and:

• 如果进位+ A [i] + B [i] == 2 表示该位标志着进位序列的开始，因此 ++ curr_carry_sequence 和 carry = 1 。


• 如果进位+ A [i] + B [i] == 3 表示由前一位加法转发的进位为在这里使用，该位将产生一个新的进位，因此进位序列的长度将重置为1，即 curr_carry_sequence = 1 和 carry = 1 。


• 如果进位+ A [i] + B [i] == 1或0 表示前一位生成的进位在此处解析并且它将标记进位序列的结尾，因此进位序列的长度将重置为0。即 curr_carry_sequence = 0 和 carry = 0 。

• if carry + A[i] + B[i] == 2 means that bit marks the start of carry-sequence, so ++curr_carry_sequence and carry = 1.
• if carry + A[i] + B[i] == 3 means the carry which was forwarded by previous bit addition is consumed here and this bit will generate a new carry so, length of carry-sequence will reset to 1 i.e. curr_carry_sequence = 1 and carry = 1.
• if carry + A[i] + B[i] == 1 or 0 means carry generated by the previous bit resolves here and it will mark the end of the carry-sequence, so the length of the carry-sequence will reset to 0. i.e. curr_carry_sequence = 0 and carry = 0.

现在，如果 curr_carry_seq 长度是> 比 max_carry_sequence ，然后更新 max_carry_sequence 。

Now if curr_carry_seq length is > than max_carry_sequence, then you update the max_carry_sequence.

答案为 max_carry_sequence + 1 。

有关源代码，请参考无进位加法器解决方案。

For Source-code refer to No Carry Adder Solution.

P.S。有关无运载工具添加器的平均情况分析，请参阅以下文章：无进位加法器的平均案例分析： log（n）+ O（1）平均步数：简单分析。

P.S. For average-case analysis of No-Carry Adder you can refer to the paper: Average Case Analysis of No Carry Adder: Addition in log(n) + O(1)Steps on Average: A Simple Analysis.

这篇关于while循环将执行多少次？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！