In der Computerprogrammierung ist der XOR-Tausch ein Algorithmus, der den XOR bitwise Operation verwendet, um Werte verschiedener Variablen zu tauschen, die denselben Datentyp haben, ohne eine vorläufige Variable zu verwenden. "Verschieden" bedeutet, dass die Variablen an verschiedenen Speicheradressen versorgt werden; die Ist-Werte der Variablen müssen nicht verschieden sein.

Der Algorithmus

Das herkömmliche Tauschen verlangt den Gebrauch einer vorläufigen Lagerungsvariable. Mit dem XOR-Tausch-Algorithmus, jedoch, ist keine vorläufige Lagerung erforderlich. Der Algorithmus ist wie folgt:

X: = X XOR Y

Y: = Y XOR X

X: = X XOR Y

</syntaxhighlight>

Der Algorithmus entspricht normalerweise drei Maschinencodeinstruktionen. Da XOR eine Ersatzoperation ist, können X XOR Y durch Y XOR X in einigen der Linien ersetzt werden. Wenn codiert, auf der Zusammenbau-Sprache wird dieser commutativity häufig in der zweiten Linie ausgeübt:

Im obengenannten System/370 codiert Zusammenbau Probe, R1 und R2 sind verschiedene Register, und jede XR Operation verlässt sein Ergebnis im im ersten Argument genannten Register. Mit x86 Zusammenbau sind Werte X und Y in Registern eax und ebx (beziehungsweise), und legt das Ergebnis der Operation im zweiten Register.

Jedoch scheitert der Algorithmus, wenn x und y dasselbe Speicherelement verwenden, seitdem der Wert in dieser Position versorgt hat, wird zeroed durch die erste XOR Instruktion sein, und dann Null bleiben; es wird mit sich nicht "getauscht". (Bemerken Sie, dass das nicht dasselbe ist, als ob x und y dieselben Werte haben. Die Schwierigkeiten kommen nur, wenn x und y dasselbe Speicherelement verwenden, in welchem Fall ihre Werte bereits gleich sein müssen.)

Beweis der Genauigkeit

Der binäre Operations-XOR über Bit-Schnuren der Länge stellt die folgenden Eigenschaften aus (wo XOR anzeigt):

• L1. Commutativity:
• L2. Associativity:
• L3. Identität besteht: Es gibt wenig Schnur, 0, (der Länge N) solch das für jeden
• L4. Jedes Element ist sein eigenes Gegenteil: für jeden.

Nehmen Sie an, dass wir zwei verschiedene Register und als im Tisch unten, mit Anfangswerten A und B beziehungsweise haben. Wir führen die Operationen unten in der Folge durch, und reduzieren unsere Ergebnisse mit den Eigenschaften, die oben verzeichnet sind.

Codebeispiel

Eine C-Funktion, die den XOR-Tausch-Algorithmus durchführt:

Leere xorSwap (interne Nummer *x, interne Nummer *y) {\

wenn (x! = y) {\

*x ^ = *y;

*y ^ = *x;

*x ^ = *y;

}\

}\

</Quelle>

Bemerken Sie, dass der Code nicht tauscht, sind die ganzen Zahlen sofort gegangen, aber überprüfen zuerst, ob ihre Adressen verschieden sind. Das ist, weil, wenn die Adressen gleich sind, sich der Algorithmus zu einem dreifachen *x ^ = *x falten wird, auf Null hinauslaufend.

Der Körper dieser Funktion wird manchmal falsch verkürzt dazu gesehen. Dieser Code hat unbestimmtes Verhalten, da es den lvalue zweimal ohne einen vorläufigen Folge-Punkt modifiziert.

Gründe für den Gebrauch in der Praxis

In den meisten praktischen Drehbüchern ist der triviale Tausch-Algorithmus mit einem Zwischenregister effizienter. Beschränkte Situationen, in denen tauschender XOR praktisch sein kann, schließen ein:

• Auf einem Verarbeiter, wo die Befehlssatz-Verschlüsselung dem XOR-Tausch erlaubt, in einer kleineren Zahl von Bytes verschlüsselt zu werden;
• In einem Gebiet mit dem hohen Register-Druck kann es dem Register-Verteiler erlauben zu vermeiden, ein Register zu verschütten.
• In Mikrokontrolleuren, wo verfügbarer RAM sehr beschränkt wird.

Weil diese Situationen selten sind, erzeugen die meisten Optimierungsbearbeiter XOR-Tausch-Code nicht.

Gründe für die Aufhebung in der Praxis

Die meisten modernen Bearbeiter können weg die vorläufige Variable im naiven Tausch optimieren, in welchem Fall der naive Tausch denselben Betrag des Gedächtnisses und dieselbe Zahl von Registern verwendet, wie die XOR tauschen und mindestens als schnell, und häufig schneller ist. Der XOR-Tausch ist auch viel weniger lesbar und zu jedem völlig undurchsichtig, der mit der Technik fremd ist.

Auf modernen Zentraleinheitsarchitekturen ist die XOR Technik beträchtlich langsamer als das Verwenden einer vorläufigen Variable, um das Tauschen zu tun. Ein Grund besteht darin, dass sich moderne Zentraleinheiten mühen, Instruktionen in der Parallele über Instruktionsrohrleitungen durchzuführen. In der XOR Technik hängen die Eingänge zu jeder Operation von den Ergebnissen der vorherigen Operation ab, so müssen sie in der ausschließlich folgenden Ordnung durchgeführt werden. Wenn Leistungsfähigkeit von enormer Bedeutung ist, wird es empfohlen, die Geschwindigkeiten sowohl der XOR Technik als auch des vorläufigen variablen Tauschens auf der Zielarchitektur zu prüfen.

Optimierung des XOR-Tausches und der Alternativen

Moderne Optimierungsbearbeiter arbeiten durch das Übersetzen des Codes, der ihnen in eine innere Fluss-basierte Darstellung gegeben wird, die sie auf viele Weisen vor dem Produzieren ihrer Maschinencode-Produktion umgestalten. Diese Bearbeiter werden mit größerer Wahrscheinlichkeit anerkennen und einen herkömmlichen (vorläufigen) Tausch optimieren als, die Behauptungen der höheren Programmiersprache anzuerkennen, die einem XOR-Tausch entsprechen. Oft, was geschrieben wird, weil ein Tausch im Code auf höchster Ebene durch den Bearbeiter in ein einfaches inneres Zeichen übersetzt wird, dass zwei Variablen Speicheradressen, aber nicht jeden Betrag des Maschinencodes getauscht haben. Andere Zeiten, wenn die Zielarchitektur es unterstützt und ist es vorzuziehend, der Bearbeiter kann eine einzelne Instruktion des Tausches/Austausches verwenden (wie x86's XCHG), der den Tausch in einer einzelnen Operation durchführt.

Aliasing

Der XOR-Tausch wird auch in der Praxis durch aliasing kompliziert. Wie bemerkt, oben, wenn ein Versuch gemacht wird, den Inhalt von einer Position mit sich Zu XOR-tauschen, besteht das Ergebnis darin, dass die Position zeroed und sein verlorener Wert ist. Deshalb muss tauschender XOR nicht blind auf einer höheren Programmiersprache verwendet werden, wenn aliasing möglich ist.

Schwankungen

Der zu Grunde liegende Grundsatz des XOR-Tausch-Algorithmus kann auf irgendwelche Operationsentsprechen-Kriterien L1 durch L4 oben angewandt werden. Das Ersetzen von XOR durch die Hinzufügung und Subtraktion gibt eine ein bisschen verschiedene aber größtenteils gleichwertige, Formulierung:

Leere addSwap (nicht unterzeichnete interne Nummer *x, nicht unterzeichnete interne Nummer *y)

{\

wenn (x! = y) {\

*x = *x + *y;

*y = *x - *y;

*x = *x - *y;

}\ }\</Quelle>

Verschieden vom XOR-Tausch verlangt diese Schwankung, dass der zu Grunde liegende Verarbeiter oder die Programmiersprache eine Methode wie Modularithmetik oder bignums verwenden, um zu versichern, dass die Berechnung dessen keinen Fehler wegen der Überschwemmung der ganzen Zahl verursachen kann. Deshalb wird es noch seltener in der Praxis gesehen als der XOR-Tausch.

Zeichen

Siehe auch

• Symmetrischer Unterschied
• XOR hat Liste verbunden
• Ziffer von Feistel (ist der XOR-Tausch-Algorithmus eine degenerierte Form von Feistel cypher)