Strona główna » Algorytmy » Artykuły » Swap z użyciem XOR

Swap 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.Zamiana 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:

pqp XOR q
000
101
011
110

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:

a1011
b0100
a XOR b1111

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:

b0100
a1111
b XOR a1011

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:

a1111
b1011
a XOR b0100

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.