Skip to content

Program to add two numbers without using any arithmetic operators

January 17, 2011

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!

About these ads
5 Comments
  1. Narayanan permalink

    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.

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

  3. sanju permalink

    thanks for explaining
    I really appreciate it

  4. 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?”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: