Make the frequent cases fast and the rare case correct

Program to add two numbers without using any arithmetic operators

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 .

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
0001 — with XOR

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

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");
	printf("enter the second number\n");
	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

laptop:~/code$ ./a.out
Enter the first number
enter the second number
the sum is : 1276

laptop:~/code$ ./a.out
Enter the first number
enter the second number
the sum is : 79

Thanks for reading!

About these ads

6 responses to “Program to add two numbers without using any arithmetic operators

  1. Narayanan January 5, 2012 at 8:10 pm

    Write the explanation in a clear way …

    • chinmaylokesh January 19, 2013 at 3:38 pm

      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. chinmaylokesh February 14, 2012 at 3:17 am

    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 June 6, 2012 at 11:30 am

    thanks for explaining
    I really appreciate it

  4. Birendra Kumar Sah March 4, 2013 at 2:03 pm

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

  5. Santosh October 2, 2014 at 2:38 am

    good explanation!!!! :)

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

%d bloggers like this: