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

  • Aviator + Websockets

    15.06.2019

    Nachdem ich in den letzten Wochen und Monaten meine Zeit und Energie in die sQLshell gesteckt habe - was sowohl Bugfixing als auch neue Features betraf - habe ich nun endlich die Zeit gefunden, ein bereits lange überfälliges Feature an dWb+ und speziell am aviator zu implementieren.

    Weiterlesen...

Neueste Artikel

  • Neue Version plantumlinterfaceproxy napkin look

    Es gibt eine neue Version des Projektes plantumlinterfaceproxy - Codename napkin look.

    Weiterlesen...
  • Apache HTTPCore5 funktioniert nicht mit Docker

    Ich habe neulich drei Stunden meines Lebens verschwendet weil ich unbedingt die neueste Version der HTTPCore5 Library von Apache einsetzen wollte.

    Weiterlesen...
  • Entwurfsmodus für beliebige SVG Graphiken

    Nachdem ich in der Vergangenheit immer wieder Weiterentwicklungen der Idee vorgestellt habe, Graphiken mit dem Computer so zu ezeugen dass sie eine gewisse "handgemachte" Anmutung haben, habe ich nunmehr die durchschlagende Idee gehabt:

    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.