Zamiana wartości dwóch zmiennych bez użycia trzeciej zmiennej pomocnicze [C++]

Jest to częsty problem algorytmiczny zadawany czy to studentom informatyki przez wykładowców jak i rekruterów na różnych rozmowach o prace. Problem nie jest w cale trudny jak by się mogło wydawać.


Najprostszym sposobem jest wykorzystanie dodawania i odejmowania liczb. Oczywiście w umiejętny sposób będziemy wykonywać te działania. Algorytm bazuje na zauważeniu jak się mają dwie liczby przeciwne do siebie oraz wykorzystuje własności liczb na osi liczbowej.



Przykładowy kod rozwiązujący to zagadnienie w ten sposób :

	#include <iostream>
	using namespace std;
	int main() {
	int a,b;
	cin>>a>>b;
	cout<<"Przed zamiana:"<<endl;
	cout<<a<<" "<<b<<endl;
	a = a - b;
	b = b + a;
	a = b - a;
	cout<<"Po zamianie:"<<endl;
	cout<<a<<" "<<b<<endl;
	return 0;
	}

view raw Swap 2 variable without temporary summation.cpp hosted with ❤ by GitHub

Niestety operacje zarówno dodawania jak i odejmowania nie są zbytnio wydajne. Należy również zwrócić uwagę na fakt wczytania do zmiennych zbyt dużych liczb które mieszczą się w danym typie lecz po zastosowaniu operacji arytmetycznych mogą spowodować przepełnienie wartości zmiennej i tym samym zakłamanie wyniku.

Lepszym pomysłem będzie wykorzystanie do zamiany wartości zmiennych, alternatywy wykluczającej czyli inaczej zwanej funkcją logiczną XOR. Funkcja ta jest prawdziwa tylko w przypadku gdy mamy dwa różne znaki np 1 i 0 lub 0 i 1. W pozostałych przypadkach jest fałszywa. Tabelka poniżej ilustruje działanie funkcji XOR.

A	B	Y
1	1	0
1	0	1
0	1	1
0	0	0

W języku C++ funkcja XOR jest realizowana za pomocą operatora '^'.

Przykładowy program zamieniający wartości wykorzystujący funkcję XOR

	#include <iostream>
	using namespace std;
	int main() {
	int a,b;
	cin>>a>>b;
	cout<<"Przed zamiana:"<<endl;
	cout<<a<<" "<<b<<endl;
	a=a^b;
	b=b^a;
	a=a^b;
	cout<<"Po zamianie:"<<endl;
	cout<<a<<" "<<b<<endl;
	return 0;
	}

view raw Swap 2 variable without temporary XOR.cpp hosted with ❤ by GitHub