L'aggiunta di due numeri senza operatore + (chiarificazione)

Question

So che possiamo usare la logica dell'addizionatore binario dove Somma = a XOR b e vai = a AND b Ho anche avuto una soluzione:

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

Quello che non capisco qui è perché il carry bit è spostato, o moltiplicato per 2 durante ogni ricorsione?

Answer 1

Trovo questo un po 'difficile da spiegare, ma ecco un tentativo; pensa un po 'alla volta, ci sono solo 4 casi;

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

Le due linee di gestire differenti casi

sum = a^b 

Maniglie caso 0 + 1 e 1 + 0, somma conterrà caso semplice, tutte le posizioni di bit che sommano 1.

carry = (a & b) << 1 

Il (a & b) parte trova tutte le posizioni di bit con il caso 1 + 1. Poiché l'aggiunta risulta in 0, è il carry che è importante, e viene spostato nella posizione successiva a sinistra (< < 1). Il carry deve essere aggiunto a quella posizione, quindi l'algoritmo ricomincia.

L'algoritmo si ripete fino a quando non ci sono più trasporta, nel qual caso la somma conterrà il risultato corretto.

Btw, return sum dovrebbe essere return a, quindi sia sum sia carry potrebbero essere variabili locali regolari.

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

Ciao, non pensarti troppo difficile. Ecco il modo semplice per farlo.

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

che è.