Wie man Zahlen ohne +

hinzufügen Ich wurde diese Frage zu dem Interview gestellt. Ich habe nicht geantwortet und eigentlich verstehe ich nicht, wie es funktioniert.Wie man Zahlen ohne +

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

Ich frage nicht, warum es eine richtige Antwort produziert ... Zunächst einmal, warum stoppt der Algorithmus schließlich? Für mich ist das nicht so offensichtlich.

Damit es anhalten kann, muss carry0 werden. Kann das nicht auf den Punkt gebracht werden?

Quelle

2016-05-26 Alupkers

+11

Es ist ein [Volladdierer] (https://en.wikipedia.org/wiki/Adder_%28electronics%29#Full_adder). Nachdem Sie 32 Mal nach links geschoben haben, gibt es 32 Null-Bits (was "0" ist). –

@ElliottFrisch Nun ... ja)). Aber es wird nicht erklärt, warum es funktioniert. – Alupkers

@Alupkers Sie fragte, warum Algorithmus stoppt? Genau wie @ElliottFrisch sagte: 'curry << 1 'setzt das am weitesten rechts liegende Bit auf 0. In höchstens 32 Schritten (ganze Zahlen sind 32 Bit breit in Java) sind alle Bits 0, also' y == 0 'und die Schleife endet . – Nikem

line 1 : int carry = x & y; 

line 2 : x = x^y; 

line 3 : y = carry << 1;

wenn x = 1; y = 2;

Binary für jede Nummer:

0 = 00

1 = 01

2 = 10

3 = 11

für Zeile 1 Code,

& (bitweise UND) Binär- und Operator kopiert ein Bit auf das Ergebnis, wenn es in beiden Operanden vorhanden

x 1 => 01

y 2 => 10

Ergebnis Trag => 00 (0)

für Zeile 2 code,

^(bitweise XOR) Binary XOR Operator kopiert das Bit, wenn es in einem Operanden gesetzt ist, aber nicht beide.

x 1 => 01

y 2 => 10

Ergebnis x => 11 (3)

für Zeile 3-Code, variable Übertrag für verschieben braucht links 1 Bit, Also jetzt tragen ist 0 => 00 und Verschiebung 1 Bit links bedeutet, dass Carry jetzt 0 ist. Das Ergebnis y ist (0). Und while-Schleife stoppen, weil y jetzt 0 ist.

Das Endergebnis für x 3.

Hope this Ihnen helfen.

Quelle

2016-05-26 04:30:35

'x & y' ist bitweise und nicht logisch und. Carry wird hier immer noch 0 sein, aber aus ganz anderen Gründen als du gesagt hast. – computerfreaker

Nehmen wir ein Beispiel:

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.

Daher ist x 22.So, x^y Speicher die Summe Teil und x & y store das Übertragsteil, und dann tragen (x & y) verschoben wird, um die Ziffer mit x^y und schließlich XOR zu verknüpfen und in x zu speichern. x ist das Ergebnis.

Quelle

2016-05-26 05:17:23 Hailey

Wenn Sie einen Volladdierer mit boolescher Logik entwerfen, erhalten Sie eine klare Antwort – Hailey

Kurz gesagt, es wird über y (und die "carrys/x & y" wird es), x zu ändern, bis es die Summe beider Ints wird.Zum Beispiel

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

Die gleiche Logik gilt für alle Werte von y anwendbar und ist nicht viel anders aus normalen hinaus nur, dass es jetzt 2 möglichen Ziffern (0 und 1) anstelle der üblichen 10 (0 zu 9).

Quelle

2016-05-26 05:58:02

Wie man Zahlen ohne +

Antwort

Verwandte Themen