la adición de dos números sin operador + (clarificación)

Question

Sé que podemos utilizar la lógica del sumador binario donde Sum = un XOR b y seguir = A y B También he conseguido una solución:

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

Lo que no entiendo aquí es ¿por qué se desplaza el bit de acarreo, o multiplicado por 2 durante cada recursión?

Answer 1

Encuentro esto un poco difícil de explicar, pero aquí hay un intento; pensar poco a poco además, solo hay 4 casos;

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

Las dos líneas manejan casos diferentes

sum = a^b 

Maneja caso 0 + 1 y 1 + 0, suma contendrá el caso sencillo, todas las posiciones de bit que se suman a 1.

carry = (a & b) << 1 

La parte (a & b) encuentra todas las posiciones de bit con el caso 1 + 1. Dado que la suma resulta en 0, es el acarreo lo que es importante, y se desplaza a la siguiente posición a la izquierda (< < 1). El acarreo debe agregarse a esa posición, por lo que el algoritmo se ejecuta nuevamente.

El algoritmo se repite hasta que no haya más acarreos, en cuyo caso sum contendrá el resultado correcto.

Btw, return sum debe ser return a, entonces tanto sum como carry podrían ser variables locales regulares.

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

Hola, no te hagas demasiado difícil. Aquí la manera simple de hacer eso.

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

eso es todo.