Zamiana wartości z użyciem XOR

Typowa zamiana

W programie niejeden raz może dojść do sytuacji kiedy trzeba zamienić wartości dwóch zmiennych. Zazwyczaj jako pierwszy sposób na rozwiązanie tego problemu podaje się następujący algorytm:

1. void swap(int &a, int &b) {
2.   int temp = a;
3.   a = b;
4.   b = temp;
5. }

Powyższy algorytm warto bardzo dokładnie przeanalizować. Po pierwsze (2.) deklarowana jest dodatkowa zmienna pomocnicza temp ma ona za zadanie zachować wartość jednej zmiennej, aby można było dokonać zamiany wartości. Wykonywane są łącznie trzy operacje przypisania. Taka metoda sprawdza się dla dowolnego typu danych.

Zmiana z XOR

Implementacja

Istnieje jednak bardziej przyjazna komputerowi metoda zamiany wartości zmiennych. Należy jednak pamiętać, że dotyczy to przede wszystkim typów prostych. Podczas korzystania z XOR nie istnieje potrzeba deklaracji dodatkowej zmiennej co pokazuje poniższy kod:

1. void swap(int &a, int &b) {
2.   a ^= b;
3.   b ^= a;
4.   a ^= b;
5. }

W tym przypadku nie istnieje dodatkowe zapotrzebowanie na pamięć i są wykonywane jedynie trzy operacje logiczne.

Wyjaśnienie

XOR w matematyce jest nazywana alternatywą wykluczającą i działa w następujący sposób:

Prześledźmy teraz zamianę wartości 11 i 4, które zapisane binarnie to odpowiednio 1011 i 0100. Pierwsza operacja polega na przypisaniu a wartości 1011 XOR 0100:

W tym momencie zmienna b ma niezmienioną wartość, a wartość zmiennej a można odczytać przy pomocy b. Druga operacja to przypisanie b wartości 0100 XOR 1111:

Warto zauważyć, że teraz sytuacja sie odwróciła: zmienna b już zawiera wartość a, a zmienna a wciąż zawiera połączenie obydwu zmiennych. Ostatni krok polega na odzyskaniu drugiej wartości poprzez operację 1111 XOR 1011:

Po zakończeniu trzeciej operacji XOR otrzymujemy, że a = 0100₂ = 4 oraz b = 1011₂ = 11.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   int a, b;
3.   cout << "Podaj wartosci\na = ";
4.   cin >> a;
5.   cout << "b = ";
6.   cin >> b;
7.   swap(a, b);
8.   cout << "Po zamianie a = " << a;
9.   cout << ", b = " << b;
10.   system("pause");
11.   return 0;
12. }

• Kod źródłowy Typowa zamiana
• Kod źródłowy Zamiana z XOR

Zadania

Zadanie 1

Napisz funkcją swap, która będzie przyjmować dwie zmienne typu int* o równej długości n. Zadanie polega na napisaniu program, który zamieni wszystkie wartości na obu listach wykorzystując do tego funkcję logiczną XOR.

• Kod źródłowy Zadanie 1