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

  • Zugriff auf Maps ohne Cast in Java

    22.11.2017

    Collections im Zusammenspiel mit Generics erlauben es, ohne Cast auf Elemente gleichen Typs typsicher zuzugreifen - was aber wenn man typsicher auf Elemente unterschiedlicher Typen in einer Collection zugreifen möchte, ohne zu casten? Hier die Vorstellung einer möglichen Antwort

    Weiterlesen...

Neueste Artikel

  • Nerd-Dictation Tests

    Ich habe vor einiger Zeit schon einmal mit Spracherkennung experimentiert und war damals enttäuscht - vielleicht aber auch deshalb, weil ich nur mäßig motiviert war und mich deshalb bereits früh abschrecken ließ, als nicht alles sofort so funktioniert hat wie ich es wollte. Nun habe ich das Thema nochmals aufgegriffen...

    Weiterlesen...
  • Struktur von PKIs re: Archivzeitstempel

    Hier nochmal eine Beleuchtung der Organisation einer Public Key Infrastructure (PKI) von einem (von mir) bisher nicht betrachteten Blickwinkel

    Weiterlesen...
  • Security QA mit Kotlin-Bibliotheken und Java

    Über die Probleme und Herausforderungen beim Unit-Testen im Security-Umfeld mit Kotlin-Bibliotheken...

    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.