Swap zweier Variablen ohne zusätzliche Variable

vorhergehende Artikel in: Java Numerik
26.03.2022

Ich bin neulich über einen Artikel gestolpert der erklärte, wie man in Programmen die Werte zweier Variablen vertauschen kann, ohne dazu eine extra Variable zur Zwischenspeicherung zu benötigen.

Ich habe in der Vergangenheit bereits über interessante, in der Numerik begründete Abkürzungen in Programmen und den Einfluss verschiedener Programmieransätze auf die Komplexität entstehenden Codes berichtet.

Daher hat mich diese Idee intereressiert. Die naive und intuitive Herangehensweise zum Tausch der Werte zweier Variablen a und b ist das bekannte

latch=a;
a=b;
b=latch;

Dazu benötigt man neben den zwei Variablen, deren Werte man tauschen möchte noch eine weitere als Zwischenspeicher. Möchte man die Nutzung einer solchen zusätzlichen Variable verhindern, kann man das erreichen - vorausgesetzt, die beiden Variablen enthalten ganzzahlige Werte und sind in der Lage, die Summe und die Differenz der beiden Werte abzubilden, ohne dass es zu einem numerischen Überlauf kommt. Dazu geht man wie folgt vor:

Setzt man ein erkennt man, dass der Tausch tatsächlich stattgefunden hat - zunächst 1 in 2:

Und nun mit 5 und 1 in 3:

Man sieht, dass die beiden Variablen a und b tatsächlich ihre Werte getauscht haben! Nachdem nun demonstriert wurde, dass es tatsächlich möglich ist - wie sinnvoll ist das? Abgesehen von der Tatsache, dass ich nur eine Notwendigkeit in der Maschinenprogrammierung sehe (Dort kann es ja vorkommen, dass manche Operationen nur auf bestimmte Register angewendet werden können und man daher Daten zwischen Registern austauschen muss), sehe ich in Hochsprachen dafür absolut keine Notwendigkeit mehr - was die ganze Sache in den Bereich des pur akademischen Interesses verlagert.

Darüber hinaus ist es so, dass die Rechenzeit dadurch nicht verringert wird, denn die Anzahl der Operationen ist immer noch dieselbe - und ob die verbrauchte Rechenzeit bei Load/Store-Instructions und bei Arithmetik-Instructions sich in aktuellen Prozessoren wirklich so sehr unterscheidet, möchte ich bezweifeln.

Dazu kommt noch, dass sich auf Maschinensprach-Ebene die beiden Varianten unter Umständen nicht mehr so sehr unterscheiden: Oft ist es ja so, dass Arithmetik mit einem Spezial-Register - dem sogenannten Akkumulator durchgeführt werden muss. Und in diesem Fall bräuchten wir wieder drei "Variablen": Die zwei Register, deren Inhalte getauscht werden sollen und den Akkumulator. Man hätte also in einer solchen Architektur nichts gewonnen. In einer Architektur mit echten General-Purpose-Registern wie der Motorola 68xxx-Serie würde die Einsparung tatsächlich wie theoretisch erklärt funktionieren - die entsprechenden Maschinenbefehle zum Tausch der Werte in den Registern d1 (a) und d2 (b) würden wie folgt aussehen:

	add	d2,d1
	sub	d2,d1
	sub d2,d1

Aber auch hier erkennt man: es werden genau wie beim Tausch mit Zwischenvariable drei Operationen gebraucht. Dazu kommt in dieser Architektur (wie wahrscheinlich in vielen anderen auch): Bedingt durch die Tatsache, dass manche Operationen nur auf bestimmten Registern funktionieren existiert ein dedizierter Maschinenbefehl EXG zum Tausch der Werte zweier Register. Das ist ein weiterer Grund, warum man solche wie die oben beschriebene Varianten nicht benutzen sollte: Den traditionellen Tausch mit Zwischenvariable kann ein Compiler erkennen und durch Benutzung solch optimierter Maschinenbefehle ersetzen. Die Variante mit der Arithmetik dagegen würde nicht davon profitieren.

Zum Abschluss nun noch eine Einsicht betreffend einer speziellen Sprache: Java. Hier zeigt sich, dass die "traditionelle" Variante deutlich schneller ist - weil der erzeugte Bytecode deutlich kürzer ist:

	public void a()
	{
		int a=10;
		int b=5;
		int c=a;
		a=b;
		b=c;
	}

ergibt:

public void a();
   Code:
      0: bipush        10
      2: istore_1
      3: iconst_5
      4: istore_2
      5: iload_1
      6: istore_3
      7: iload_2
      8: istore_1
      9: iload_3
     10: istore_2
     11: return

während

	public void b()
	{
		int a=10;
		int b=5;
		a=a+b;
		b=a-b;
		a=a-b;
	}

in folgenden Bytecode transformiert wird:

public void b();
   Code:
      0: bipush        10
      2: istore_1
      3: iconst_5
      4: istore_2
      5: iload_1
      6: iload_2
      7: iadd
      8: istore_1
      9: iload_1
     10: iload_2
     11: isub
     12: istore_2
     13: iload_1
     14: iload_2
     15: isub
     16: istore_1
     17: return

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • Brian May, Kerry Ellis & Vittorio Grigolo: Bohemian Rhapsody

    19.05.2019

    Eine andere Sicht auf den schönen Queen-Klassiker

    Weiterlesen...

Neueste Artikel

  • sQLshell, SQLite und Redis - oh my!

    Ich habe in letzter Zeit hin und wieder mit der sQLshell und SQLite herumgespielt - Neulich wurde ich gefragt, ob die sQLshell eigentlich auch Redis kann...

    Weiterlesen...
  • bad-certificates Version 3.0.0

    Das bereits vorgestellte Projekt zur automatisierten Erzeugung von Zertifikaten mit allen möglichen Fehlern wurde um eine weitere Kategorie von Zertifikaten erweitert

    Weiterlesen...
  • Erste Vor-Version eines Gis-Plugin für die sQLshell

    Wie bereits in einem früheren Artikel erwähnt plane ich, demnächst ein Plugin für die sQLshell anzubieten, das eine Visualisierung von Daten mit räumlichem Bezug im Stil eines Geoinformationssystems erlaubt.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier - meine öffentlichen GitLab-Repositories finden sich dagegen hier.