Come aggiungere numeri senza +

Mi è stata fatta questa domanda nell'intervista. Non ho risposto e in realtà non capisco come funziona.Come aggiungere numeri senza +

int add(int x, int y) 
{ 
    while (y != 0) 
    { 
     int carry = x & y; 
     x = x^y; 
     y = carry << 1; 
    } 
    return x; 
}

Non sto chiedendo perché lo fa produrre una risposta corretta ... Prima di tutto, perché l'algoritmo alla fine si fermano? Per me non è così ovvio.

Per interromperlo, carry deve diventare 0. Nessuno può spiegarlo in poche parole?

fonte

2016-05-26 Alupkers

+11

È un [full adder] (https://en.wikipedia.org/wiki/Adder_%28electronics%29#Full_adder). Dopo lo spostamento a sinistra di 32 volte, ci saranno 32 bit zero (che è '0'). –

@ElliottFrisch Beh ... sì)). Ma non è spiegato perché funzioni. – Alupkers

@Alupkers Hai chiesto perché l'algoritmo si arresta? Esattamente come @ElliottFrisch ha detto: 'curry << 1' imposta il bit più a destra su 0. In massimo 32 passi (gli interi sono a 32 bit in Java) tutti i bit sono 0 quindi' y == 0' e il ciclo termina . – Nikem

line 1 : int carry = x & y; 

line 2 : x = x^y; 

line 3 : y = carry << 1;

se x = 1; y = 2;

binaria a ciascun numero:

0 = 00

1 = 01

2 = 10

3 = 11

per 1 codice di linea,

& (bit a AND) esemplari binari ed esercente un po 'al risultato se esiste in entrambi gli operandi

x è 1 => 01

y è 2 => 10

risultato riporto è => 00 (0)

per codice di linea 2,

^(XOR bit a bit) copie binario XOR operatore il bit se si trova in un operando, ma non entrambi.

x è 1 => 01

y è 2 => 10

risultato x è => 11 (3)

codice linea 3, riporto variabile deve spostamento a sinistra per 1 bit, quindi ora carry è 0 => 00 e shift 1 bit a sinistra significa carry è ora 0. Il risultato y è (0). E mentre il ciclo si ferma perché y è 0 ora.

Il risultato finale per x è 3.

Spero che questo vi aiuterà.

fonte

2016-05-26 04:30:35

'x & y' è bit a bit e non logico. carry sarà ancora 0 qui, ma per ragioni completamente diverse da quelle che hai affermato. – computerfreaker

Facciamo un esempio:

x=13(1101) 
y=9(1001) 

Loop 1: 
----------------- 
y!=0 -> carry=(1101)&(1001)=1001(9) [AND Op] 
x=(1101)^(1001)=0100(4) [XOR Op] 
y=carry<<1 -> y=(carry)x2=10010(18) 

Loop 2: 
----------------- 
y!=0 -> carry=(0100)&(10010)=00000(0) 
x=(0100)^(10010)=10110(22) 
y=carry<<1 -> y=0 

loop terminated.

pertanto, x è 22.So, x^y negozio parte somma e x & y negozio parte di riporto, e quindi portare (x & y) viene spostata per abbinare la cifra con x^y e infine XOR e memorizzarli in x. x è il risultante.

fonte

2016-05-26 05:17:23 Hailey

Se progettate un sommatore completo con logica booleana, otterrete la risposta chiara – Hailey

In poche parole si tratta di utilizzare y (e il "trasporta/x & y" diventa) per modificare x fino a quando non diventa la somma di entrambi i valori.Ad esempio,

y=1 (....0001), x=anything (either .....0 or .....1) 
if x ends with 0, x&y=0 
    //x^y = x becomes ....001 (thereby adding 1) 
    //since x&y=0 the loop stops 
if x ends with 1, x&y=1 
    //x^y = x 
    //since y= x&y<<1, new y=(.....000010) 
    if x ends with 01, x&y=0 
     //x^y = x becomes ....010 (thereby adding 1) 
     //since x&y=0 the loop stops 
    if x ends with 11, x&y=1 
     //x^y = .....01 
     //since y= x&y<<1, new y=(......000100) 
     if x ends with 011 
      //stuff happens and x becomes ....100 (thereby adding 1) 
      //loop stops 
     if x ends with 111 
      //... 
      //if x ends with 111111, x becomes ....1000000 (thereby adding 1) 
      //if x ends with 1111111, x becomes ....10000000 (thereby adding 1) 
      //if x ends with 11111111, x becomes ....100000000 (thereby adding 1) 
      //well you get the idea

La stessa logica è applicabile a tutti i valori di y, e non è molto diverso da oltre normale che ci sono ora 2 cifre possibili (0 e 1) invece del solito 10 (0 a 9).

fonte

2016-05-26 05:58:02

Come aggiungere numeri senza +

risposta

Problemi correlati