How many times will the while loop be executed?

Question

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 
``

Answer 1

Algorithm for No Carry Adder:

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

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.

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,

• 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.

Algorithm to calculate the length of the longest carry-chain:

• 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,

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

  • 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.

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

• Answer would be max_carry_sequence + 1.

For Source-code refer to No Carry Adder Solution.

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.