Warum dieser code für addition(bitweise operation) funktioniert in java

Zunächst daran erinnern, außerdem in der Grundschule. z.B. 26 + 147 = 173. Sie starten mit der 6+7=13, so stellen Sie 3 in der Summe, und tragen, und so weiter - das heißt: Sie fügen zwei Ziffern und tragen Sie sich ein, wenn nötig.

carry:  1
a:      26
b:     147
-----------------
sum:   173

Den code hat fast die gleiche Sache auf Binär-zahlen, aber mit einem kleinen kniff. Statt einer Stelle in einer Zeit, die es braucht, alle in einem gehen. Statt das tragen von position i-1 in i (D. H. einschließlich 1, wenn das hinzufügen von 2 und 4), den code hinzufügen, alle Karies in einer zweiten iteration. Also was es tut ist: 026+147 = 163 + 010 = 173 + 000

Für die binäre zahlen a=6=00110 und b=7=00111 erhalten Sie

Ersten finden Sie die trägt; das ist alles Positionen, in denen beide a und b hat seine bit-set: int carry = (a & b) ;

Dann id noch der Zusatz von Ziffern, ignorieren Sie die tragen, und speichert es in a: a = a ^ b; Diese reagieren auf 6+7=3 im Beispiel.

Den letzten Teil verschiebt sich das tragen auf die nächste Stelle, also die Gewährleistung der 1-carry-in dem Beispiel ist "umgezogen" von der 1 auf die 10: carry << 1;

Die while-Schleife wird so lange fortgesetzt, wie es sich trägt, nicht enthalten in der Summe.

Jeden Fall denken alle zahlen in hier im binären system.

Was würden Sie in der Regel gerne, um herauszufinden, in solcher code ist ein "loop-invariant". In diesem Fall würde Man gerne sehen, dass a + b konstant ist, nach jeder iteration. So, wenn b zu 0 und wir verlassen die Schleife, ein muss, entspricht der Summe der ursprünglichen a-und b -. Der nächste Schritt ist, um sicherzustellen, dass die Schleife irgendwann beendet. Wir kommen später noch darauf zurück, lassen Sie uns zunächst herausfinden, unveränderlichen Teil, der in diesem Fall ist mit der Gleichberechtigung:

a + b = (a ^ b) + 2 * (a & b)

wo in der Schleife eine neue wird gleich alten a ^ b und b 2 * (a & b), das ist das gleiche wie (a & b) << 1. Das ist die Essenz von Deinem problem, herauszufinden, diese Gleichheit. Es ist genau, wie Sie das neben.

Zeige ich zwei Lösungen.
In beiden verwende ich eine einfache Tatsache, dass:

x + y = x ^ y

Wann immer x und y haben keinen gemeinsamen bits festgelegt.

Den kurzen Weg, um zu sehen, das formal ist zu beachten, dass:

a + b = a + b - 2(a & b) + 2(a & b)
= (a - (a & b)) + (b - (a & b)) + 2(a & b)
= (a - (a & b)) ^ (b - (a & b)) + 2(a & b)
= (a ^ (a & b)) ^ (b ^ (a & b)) + 2(a & b)
= a ^ b + 2(a & b)

Die langwierige Lösung basiert auf mathematischen Induktion folgt (dies könnte betrachtet werden ein übermaß von einigen, aber in meine option ist es Wert, es zu wissen):

Zunächst sicherstellen, dass es funktioniert mit a und b beide gleich null sind (Sie könnten auch versuchen, für eine bit-zahlen, die eine Menge erklären, wie dieser Algorithmus funktioniert). Nie vergessen Sie diesen Schritt, wenn mit Hilfe der mathematischen Induktion.

Nächsten, anzunehmen, diese Werke für die n-1-bit-zahlen, die wir bekommen haben, zu zeigen, dass es funktioniert für n bisschen zu. Jetzt schreiben a = 2a' + a" = 2a' ^ a 'und b = 2b' + b '= 2b' ^ b", wo a", b" sind in der Menge {0, 1} (dann ist 2a "und" haben keine gemeinsamen bits gesetzt!).
Dann:

(a ^ b) + 2(a & b) = (2a' ^ a'' ^ 2b' ^ b'') + 2((2a'' ^ a') & (2b'' ^ b')) =
(2a' ^ 2b') ^ (a'' ^ b'') + 2((2a'' & 2b'') ^ (a'' & b'')) = 
(2a' ^ 2b') + (a'' ^ b'') + 2((2a'' & 2b'') + (a'' & b'')) =
(2a' ^ 2b') + 2((2a'' & 2b'') + (a'' ^ b'') + (a'' & b'')) =
2a' + 2b' + a'' + b'' = a + b

Nun die Letzte Sache zu prüfen, ist, dass diese Schleife wirklich beendet.
um dies zu sehen, verwenden Sie die Tatsache, dass bei jedem Schritt a und b beide nicht negativ sind, und dass dies gilt nach jeder iteration.

Deshalb haben wir, die b <= a + b.
Weiter beachten Sie, dass nach n Schritten b hat zu enden, mit n Nullen. Daher können wir nicht mehr tun, als log_2(a+b) Schritte, da würden wir bekommen entweder b = 0 oder b = k * 2*n >= 2*n > 2**log_2(a+b) = a+b, widersprechende Annahme.
Hier ** bedeutet Potenzierung natürlich.

In Java-dieser Algorithmus funktioniert auch auf den negativen ganzen zahlen. Dieses ist, weil, wie negative Ganzzahlen gespeichert sind, in Java und in den meisten Programmiersprachen
Hier die addition und Subtraktion von signed-und unsigned-zahlen funktioniert genauso wie auf bits, also code, der funktioniert für zahlen ohne Vorzeichen werden auch für unterschrieben.

Ja, wie viele Antworten hier, es funktioniert wie rudimentär Schule Mathematik für das hinzufügen von zwei zahlen. Aber in Binärer Art und Weise.

1. Was bedeutet a&b geben Sie uns? Es gibt an allen Orten, die trigger eine nach vorne tragen. Beispiele hinzufügen 1101 und 0101, nur die
   0. und 2. position von rechts-Trigger nach vorne tragen. Also nur, dass
   wird 0101, das man durch ein&b. Aber wenn dabei tragen in normalen neben, bewegen wir uns
   eine position nach Links. Das ist der Grund, warum in der 3. Anweisung der code, der zu tragen ist, bewegt eine
   position Links. So wird tragen 01010.

2. Was bedeutet a^b geben Sie uns? Jedes bit, das zählt nicht oben enthalten ist. In den obigen Schritt, wir haben Auswirkungen der 0. und 2. bit.
   Jetzt müssen wir auf andere bits, die 1. Wird von 3.
   Recht zu geben ist 1000. Der Wert zugeordnet wird 1000.

Alles was wir jetzt tun müssen ist, fügen Sie diese wieder mit den gleichen oben genannten Schritte.

1. Hinzufügen 01010 und 01000. Nur gemeinsam ist man auf der 3. position, also eine&b bietet 01000 und führen schließlich zu 10000 nach der Schicht.

2. Zählen die verbleibenden bits, a^b wird 00010 und wird zugewiesen.

Schleife Fort. Wie tragen oben ist nicht null noch.

1. Hinzufügen von 10000 und 00010. Keine gemeinsame 1 bit. So tragen wird, wird zu 0.

2. a^b wird 10010 und wird zugewiesen.

3. Tragen als null ist, was in einem, was 10010 wird die Antwort!

Viel besser zu verstehen, mit Beispielen, kleinere Beispiele.