Wiki Home Sitemap Editieren

Zur Verdeutlichung nehme ich ein Beispiel in C++, der Trick ist aber auch mit anderen Sprachen umsetzbar.

Eine viel benutzte Funktion sieht so aus:

inline void swap( int& a, int& b )
{
  int c = a;
  a = b;
  b = c;
}

Hierbei handelt es sich um eine Implementation des sog. Ringtausches. Was viele nicht wissen ist, dass man zwei Variablen auch ohne Hilfe einer temporären Variablen vertauschen kann ('^' ist der C/C++ XOR-Operator):

inline void swap( int& a, int& b )
{
  a ^= b;  // entspricht a = a ^ b
  b ^= a;  // entspricht b = b ^ a
  a ^= b;  // entspricht a = a ^ b
}

Oder noch kürzer:

inline void swap( int& a, int& b )
{
  a ^= b ^= a ^= b;
}

Dieser Code macht sich zunutze, dass man aus a^b und a b herleiten, und aus a^b und b a herleiten kann:
b = (a ^ b) ^ a
a = (a ^ b) ^ b

Im ersten Schritt wird a^b brechnet und als a gespeichert:

a = a ^ b;

Als zweites wird nun b berechnet:
b = b ^ a;

Anschliessend kann man a berechnen:
a = a ^ b;


Letzte Änderung am Freitag, September 11, 2009 11:35:38 .

[ BackLinks ]