Der Code entspricht
%Vor% Der letzte Teil wird nur benötigt, um i zu erhöhen und j für die nächste Schleifeniteration zu dekrementieren.
Warum x ^= y; y ^= x; x ^= y funktioniert, um die Werte zu tauschen, ich weiß nicht warum , aber Sie können sehen, dass es bei 1-Bit-Werten funktioniert, indem Sie alle vier Möglichkeiten betrachten:
Sie können also sehen, dass in allen Fällen die Bits x und y vertauscht sind. Wenn die Anweisungen auf größere Ganzzahlen angewendet werden, arbeitet der Operator ^ parallel an allen Bits, so dass das Endergebnis darin besteht, dass jedes Bitpaar vertauscht wird, d. H. Die gesamten Werte werden vertauscht.
XOR-Operator hat diesen einzigartigen Operator, der als Ungleichheitsdetektor fungiert, dh nur wenn sich die zwei Bits unterscheiden, wird das Ergebnis 1 sein ist 0 .
Nehmen wir nun das Beispiel in A^B , ith Bit 1, das bedeutet, dass sich das Bit% A und B unterscheiden. Das heißt, einer von ihnen ist 1 und der andere ist 0 .
Wenn wir nun (A^B)^B machen, wenn das i-te Bit in B 0 ist, erhalten wir 1 seit 1^0 = 1 , was gleich ith bit in A ist und (A^B)^A = 0 , was ith bit in B ist.
Wenn das i-te Bit B ist, ist 1 und in A ist 0 , erneutes Austauschen findet statt.
Gleiche Logik gilt für ith bit in A^B ist 0 . Sie können es sehr leicht verfälschen.
Es ist leicht zu sehen, wie der Austausch stattfindet. Wenn Sie die ursprüngliche Zahl mit A^B xorieren, erhalten Sie die andere Zahl, da swapping für jedes der entsprechenden Bits erfolgt
Es wird erwartet, dass die folgende Routine die Werte von a und b
Lassen Sie uns analysieren, wie und warum der Austausch funktioniert.
Dafür sollten wir die Werte nicht vertauschen, sondern in separaten Variablen speichern, damit wir sehen können, was genau passiert.
%Vor%Vereinfachung der Gleichungen unter Verwendung der XOR-Eigenschaften. Überprüfen Sie XOR-Eigenschaften @ Wikipedia als Referenz
a ^ b == b ^ a ) a ^ (b ^ c) == (a ^ b) ^ c ) a ^ a == 0 0 ^ a == a %Vor%
Wie Sie sehen können, enthält b1 nun den ursprünglichen Wert von a und a1 enthält den ursprünglichen Wert von b , dh die Werte von b und a werden getauscht
Zusammenfassend ist a^=b;b^=a;a^=b nur ein idiomatischer Ausdruck, nichts Magisches darin:)
XOR setzt die Bits, wenn die Operand-Bits nicht übereinstimmen, und setzt die Bits andernfalls zurück
Lassen Sie uns durch die Transformationen gehen, die mit einem Beispiel stattfinden. Nehmen wir an, wir haben die folgenden Zahlen (binär) den Variablen zugewiesen.
%Vor% Schritt # 1 : a = a ^ b // EINE MASKE ERSTELLEN
Stellen Sie sich vor der neue Wert von a ist eine Maske zum Generieren des alten Wertes von a gegeben b oder erzeugt den alten Wert von b gegeben a .
Schritt # 2 : b = b ^ a // Wiederherstellen des ursprünglichen Wertes von a unter Verwendung der Maske und des ursprünglichen Wertes von b
Da b noch immer erhalten bleibt, können wir den ursprünglichen Wert von a mit der Maske wiederherstellen - was wir in diesem Schritt getan haben
Schritt # 3 : a = a ^ b // Wiederherstellen des ursprünglichen Wertes von b unter Verwendung der Maske und des ursprünglichen Wertes von a
Nun haben wir den ursprünglichen Wert von a in der Variablen b , so dass wir mit derselben Maske den ursprünglichen Wert von b wiederherstellen können. Wir können die Maske jetzt überschreiben, da wir nach diesem Schritt die Maske nicht benötigen.
Wenn Sie zustimmen, dass y == (x^y)^x == x^(y^x) , dann haben Sie die Antwort.
Betrachten Sie eine abstrakte Version des Schleifenkörpers in dem Code, den Sie angegeben haben:
%Vor%Benennen Sie jetzt einen Wert um, um zu verdeutlichen, was passiert:
%Vor% Nun beachten Sie, dass der Code funktioniert, wenn a_xor_b dieselbe Variable ist wie a .
Es mag einfacher sein, zuerst eine andere (aber eng verwandte) Art des Tausches zweier Zahlenwerte a und b :
Dies funktioniert sowohl mit reinen Zahlen mit beliebiger Genauigkeit als auch mit ganzen Zahlen modulo N (Ganzzahlen, die sich umwickeln, wenn sie zu groß oder zu klein werden, wie sie es in Java tun).
Um dies mathematisch zu analysieren, sollten wir jedes Mal, wenn sich ein Wert ändert, ein neues Symbol zuweisen, so dass = mathematische Gleichheit anstelle von Zuweisung darstellen kann. Dann ist es nur eine Frage der grundlegenden Algebra.
Was ist mit XOR? Eine Möglichkeit, XOR zu erklären, besteht darin, es als binäre Addition zu betrachten, ohne es zu tragen. Das Ausführen eines Tauschs mit XOR ist dann gleichbedeutend mit dem oben beschriebenen "Additionstausch" für jedes Bit Modulo 2. Der Ausdruck kann jedoch vereinfacht werden, da zusätzlich Modulo 2 jede Zahl ihre eigene Inverse ist (äquivalent Addition und Subtraktion) das Gleiche). Dies (mit Kommutativität) gibt uns das Vertraute:
%Vor%Im Allgemeinen kann der obige "addition swap" in jeder mathematischen Gruppe durchgeführt werden (auch wenn dies der Fall ist) ist nicht-kommutativ - im Grunde nur Assoziativität und Inversen benötigt werden). Eine andere Denkweise von XOR ist nur, dass es eine Gruppenstruktur auf den n-Bit-Ganzzahlen induziert, und so funktioniert das Tauschen genauso wie in jeder anderen Gruppe.
Tags und Links algorithm java bitwise-xor