Sunday, April 01, 2007

Addition without using any arthmetic operator

Often is this puzzle brought up to test someone's 'bits' knowledge but it is rather straight forward to add two numbers (whole numbers).

It works by same principle as we do it by Hand, i.e. add two numbers, Keep the carry and add it into the sum. In programming we can do it achieve the simple 'addition' via XOR operator i.e. ^ and the carry can be obtained by AND Operation on both numbers and giving them one left shift. While doing it via recurstivity it may can take more than one calls to the function .

int Addition(float a, float b)
if(a==0) return b; // check if first Digit is Zero, if yes then we are done
if(b==0) return a; // Same as above, check if second Digit is Zero we are done.
gcounter++; // a global Counter to see how many times was the Additiona function called.
float sum = a^b;
float carry = (a & b) <<1;

cout<<"SUM : "<<sum<<endl;
cout<<"carry : "<<carry<<endl;
return Addition(sum, carry);
The time and space complexity would approximately be log(n).


No comments: