Adding two numbers without + operator (Clarificati

问题:

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?

回答1:

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.

回答2:

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;     
    }
}

回答3:

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.