Inselraus: Variablen mit Xor vertauschen

Eine besonders trickreiche Idee für das Vertauschen von Variableninhalten arbeitet mit dem Xor-Operator und benötigt keine temporäre Zwischenvariable. Die Zeilen zum Vertauschen von x und y lauten wie folgt:

int x = 12, 
  
    y = 49;
x ^= y; // x = x ^ y = 001100bin ^ 110001bin = 111101bin
y ^= x; // y = y ^ x = 110001bin ^ 111101bin = 001100bin
x ^= y; // x = x ^ y = 111101bin ^ 001100bin = 110001bin
System.out.println( x + " " + y );  // Ausgabe ist: 49 12

Der Trick funktioniert, da wir mit Xor etwas »hinein- und herausrechnen« können. Zuerst rechnet die erste Zeile das y in das x. Wenn wir anschließend die Zuweisung an das y machen, dann ist das der letzte schreibende Zugriff auf y, also muss hier schon das vertauschte Ergebnis stehen. Das stimmt auch, denn expandieren wir die zweite Zeile, steht dort: »y ^ x wird zugewiesen an y«, und dies ist y ^ (x ^ y). Der letzte Ausdruck verkürzt sich zu y = x, da aus der Definition des Xor-Operators für einen Wert a hervorgeht: a ^ a = 0. Die Zuweisung hätten wir zwar gleich so schreiben können, aber dann wäre der Wert von y verloren gegangen. Der steckt aber noch in x aus der ersten Zuweisung. Betrachten wir daher die letzte Zeile x ^ y: y hat den Startwert von x, doch in x steckt ein Xor-y. Daher ergibt x ^ y den Wert x ^ x ^ y, und der verkürzt sich zu y. Demnach haben wir den Inhalt der Variablen vertauscht. Im Übrigen können wir für die drei Xor-Zeilen alternativ schreiben:

y ^= x ^= y;   // Auswertung automatisch y ^= (x ^= y) 
  
x ^= y;

Da liegt es doch nahe, die Ausdrücke weiter abzukürzen zu x ^= y ^= x ^= y. Doch leider ist das falsch (es kommt für x immer null heraus). Motivierten Lesern bleibt dies als Denksportaufgabe überlassen.

Über Christian Ullenboom

Ich bin Christian Ullenboom und Autor der Bücher ›Java ist auch eine Insel. Einführung, Ausbildung, Praxis‹ und ›Java SE 8 Standard-Bibliothek. Das Handbuch für Java-Entwickler‹. Seit 1997 berate ich Unternehmen im Einsatz von Java. Sun ernannte mich 2005 zum ›Java-Champion‹.

5 thoughts on “Inselraus: Variablen mit Xor vertauschen

  1. @foomatic: Das dachte ich auch als ich das gelesen habe.

    Die Kunst ist nicht Code zu schreiben, den der Computer versteht – jeder kann kryptischen Code schreiben -, sondern Code, den Menschen verstehen.
    Da kann er auch noch so clever/performant/speichersparend sein.

  2. In einer Zeile geht es angeblich so: „y=(x^=(y^=x))^y;“
    Buchtipp: Java Puzzlers, Puzzle 7: „Swap Meat“

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.