Question

function add(A, B):
    while B is greater than 0:
        U = A XOR B
        V = A AND B
        A = U
        B = V * 2
    return A 

The above is an algorithm to add two non-negative integers A and B.

A and B are binary numbers. They have been inputted as strings.

Given the initial values of A and B write an efficient C++ program to find out the number of times the while loop of the algorithm is repeated.

Answer 1

#include <bits/stdc++.h>

using namespace std;

int cnt;

string add(string a, string b)//the function to add the two binary numbers

{

bool ok=false;//this will store the condition for the while loop

for(int i=0;i<b.size();i++)//ok will be true if string b contains atleast one zero

if(b[i]=='1')

{

ok=true;

break;

}

if(a.size()>b.size())//if the two strings are of different size then making them of same size by adding zeroes before them

{

int diff=a.size()-b.size();

for(int i=0;i<diff;i++)b='0'+b;

}

else if(a.size()<b.size())

{

int diff=b.size()-a.size();

for(int i=0;i<diff;i++)a='0'+a;

}

while(ok)

{

cnt++;

//in this while loop we are doing what we are asked to do

string u="";

string v="";

int na=a.size();

int nb=b.size();

int offset=0;

if(nb>na)//if size of b has become greater because of carry

{

u+=b[0];

offset=1;

}

for(int i=0;i<na;i++)

{

if(a[i]=='1'&&b[i+offset]=='1')//for and, xor operations

{

v+='1';//and

u+='0';//xor

}

else if(a[i]=='1'||b[i+offset]=='1')

{

u+='1';//xor

v+='0';//and

}

else

{

u+='0';//xor

v+='0';//and

}

}

a=u;

b=v+'0';//to multiply v by two we need to add a zero to the string

ok=false;

for(int i=0;i<b.size();i++)if(b[i]=='1')//checking if there is a one in string b

{

ok=true;

break;

}

}

return a;//returning the answer

}

int main()

{

string a, b;

cin>>a>>b;

cnt=0;

//printing the answers

cout<<"Sum is : "<<add(a, b)<<endl;

cout<<"No. of times loop ran is "<<cnt<<endl;

return 0;

}