Добавление двух чисел без оператора + (уточнение)

Question

Я знаю, что мы можем использовать логику двоичного сумматора, где Sum = a XOR b и Carry = a AND b

У меня также есть решение:

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

Чего я здесь не понимаю, так это почему бит переноса сдвигается или умножается на 2 во время каждой рекурсии?

Answer 1

Я считаю, что это немного сложно объяснить, но вот попытка; Подумайте о том, что поэтапно сложилось только 4 случая;

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

Две строки обрабатывают разные случаи

sum = a ^ b

Обрабатывает регистры 0 + 1 и 1 + 0, сумма будет содержать простой регистр, все битовые позиции, которые складываются до 1.

carry = (a & b) << 1

Часть (a & b) находит все битовые позиции в регистре 1 + 1. Поскольку сложение приводит к 0, важен перенос, и он перемещается в следующую позицию влево (<< 1). К этой позиции необходимо добавить перенос, чтобы алгоритм снова запустился. </p>

Алгоритм повторяется до тех пор, пока больше не будет переносов, и в этом случае сумма будет содержать правильный результат.

Кстати, return sum должно быть return a, тогда и sum, и carry могут быть обычными локальными переменными.

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

Answer 3

Привет, не думай, что ты слишком сложен.Вот простой способ сделать это.

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

вот и все.