The algorithm implements concepts of basic Base 10 addition with a twist. The twist is we need to visualize this basic addition in terms of binary computation.

So lets begin the Base 10 calculation: To add 578+698

1. Add them but do not carry, so we get 166

2. Now add again but this time list out the carry’s i.e 1110

3. Add them both 1110+166 = 1276

Similarly in Binary we can achieve this

1. Add them but do not carry, for bits in A if we have 0 and bits in B we have 0 , we have result 0 , similarly 1 and 1 we have 0, for others we get 1 irrespective of XOR or simple addition .

XOR

0 0 0

0 1 1 — we get this even with normal addition

1 0 1 — we get this with normal addition

1 1 0

so its best to use a XOR here to get 166.

Let us try on two numbers 2 and 3

0010

0011

——

0001 — with XOR

0010

0011

———

0001 — addition by ignoring carrying

so we get the same number and hence use XOR

2.Now add considering only carry. we have carry 1 if previous values added were 1 and 1 of the two numbers. this is like AND and left shift once

1

1

—-

10 — 1 AND 1 = 1 and left shift of 1 is 10

3. Do this recursively till there is nothing to carry

#include "stdio.h"
int main()
{
int num1,num2,value;
printf("Enter the first number\n");
scanf("%d",&num1);
printf("enter the second number\n");
scanf("%d",&num2);
value = add(&num1,&num2);
printf("the sum is : %d\n",value);
return 0;
}
int add(int *a,int *b)
{
int sum,carry;
if (*b == 0) return *a;
sum = *a ^ *b; // add without carrying
carry = (*a & *b) << 1; // carry, but donâ€™t add
return add(&sum,&carry); // recurse
}

OUTPUT:

laptop:~/code$ ./a.out

Enter the first number

578

enter the second number

698

the sum is : 1276

laptop:~/code$ ./a.out

Enter the first number

34

enter the second number

45

the sum is : 79

Thanks for reading!

### Like this:

Like Loading...

*Related*

Write the explanation in a clear way …

By the way if you have solid fundamental knowledge of bit operations then i believe this algorithm is cake walk even if you are reading half way through the article. I have given my best possible explanation, you are welcome to improve the article by submitting a reply with your explanation and i will put it up. I cannot improve the article with vague comments such as these.

I am not sure which part has created confusion, if you could specify which part i could explain well. However i would again like to say that in brief

Firstly ,a XOR operation on two binary numbers yields the same result as you get from doing an addition by ignoring the carry.

Secondly, if we AND two binary numbers and do a one left shift operation, its equivalent to the carry’s we get when adding two binary numbers

for example numbers 2 + 3

2 = 0010

3 = 0011

step 1 : add but don’t consider carry’s (XOR)

0010 XOR 0011 = 0001

step 2 : addition but consider only carries (AND and left shift)

0010 AND 0011 = 0010 << 1 = 0100 (list of carry's)

step 3 : pass add = 1 and carry = 4 again to the function and in next pass carry's will be zero. thus ending the recursion.

if u notice in the two passes of recursion

1st pass

0001 (after step1)

0100 (after step 2)

=

0101 = 5

2nd pass (input : 0001 ,0100)

0101 (after step1)

0000 (after step2)

since we got 0000 then our result must be 0101. We try to accumulate the result in variable a

thanks for explaining

I really appreciate it

I understand the logic but I cann’t understand the last statement of c,i.e. how the recursive process will take place( but its explained in 2nd pass of ur comment) .And also i’ll like 2 get rply about “Can we use add instruction in C?”.

good explanation!!!!