Java Blog für Programmierer

Inselraus: Variablen mit Xor vertauschen

27.05.2012 · Christian Ullenboom

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.

Kategorien: Insel