Adding two numbers without + operator (Clarification)

Question

I know that we can use the logic of binary adder where Sum = a XOR b and Carry = a AND b

I have also got a solution:

int add(int a, int b)
{
     if(b == 0)
         return sum;
     sum = a ^ b;
     carry = (a & b) << 1;
     return add(sum,carry);
}

What I don't understand here is why is the carry bit shifted, or multiplied by 2 during each recursion?

Your code has problems, for example sum and carry are undefined. I'm assuming they are globals — jim mcnamara, Jan 30 '12 at 21:31
Possible duplicate of [What is the best way to add two numbers without using the + operator?](https://stackoverflow.com/questions/365522/what-is-the-best-way-to-add-two-numbers-without-using-the-operator) — phuclv, Jun 16 '18 at 12:51

score 50 · Accepted Answer · answered Jan 30 '12 at 22:00

I find this a bit tricky to explain, but here's an attempt; think bit by bit addition, there are only 4 cases;

0+0=0 
0+1=1 
1+0=1 
1+1=0 (and generates carry)

The two lines handle different cases

sum = a ^ b

Handles case 0+1 and 1+0, sum will contain the simple case, all bit positions that add up to 1.

carry = (a & b) << 1

The (a & b) part finds all bit positions with the case 1+1. Since the addition results in 0, it's the carry that's important, and it's shifted to the next position to the left (<<1). The carry needs to be added to that position, so the algorithm runs again.

The algorithm repeats until there are no more carries, in which case sum will contain the correct result.

Btw, return sum should be return a, then both sum and carry could be regular local variables.

score 1 · Answer 2 · edited Jun 16 '18 at 12:47

public class AddSub {

    int sum=0,carry=0;
    public static void main(String[] args) {
        System.out.println("Add "+new AddSub().addition(93,5));
        System.out.println("Sub "+new AddSub().subtraction(7,60));
        System.out.println("Sub "+new AddSub().multiplication(9,60));
    }

    public int addition(int a, int b)
    {
        if(b==0)
        {
            return a;
        }
        else
        {
             sum = a^b;
             carry = (a&b)<<1;
            return addition(sum,carry);         
        }
    }

    public int subtraction(int a, int b){

        return addition(a,addition(~b,1));

    }

    public int multiplication(int a, int b){       
        for(int i=0;i<b/2;i++)
            sum = addition(sum,addition(a,a));
        return sum;     
    }
}

score 0 · Answer 3 · edited Jun 16 '18 at 12:45

0

Hi don't be think yourself too difficult. Here the simple way to do that.

Consider a=5, b=10;
c=a-(-b);
c=15;

that is it.

edited Jun 16 '18 at 12:45

phuclv

37,963
15
156
475

answered Mar 21 '16 at 11:04

Sarathi

33
1

Adding two numbers without + operator (Clarification)

3 Answers3

Linked