Strona Główna » Artykuły » Zamiana wartości z użyciem XOR

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
2
3
4
5
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

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

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
2
3
4
5
void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

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

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 1011XOR0100:

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 0100XOR1111:

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ę 1111XOR1011:

b1111
a1011
b XOR a0100

Po zakończeniu trzeciej operacji XOR otrzymujemy, że a = 01002= 4 oraz b = 10112= 11.

Testowanie funkcji

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
        static void Main(string[] args) {
            int a, b;
            Console.Write("Podaj wartości\na = ");
            a = Convert.ToInt32(Console.ReadLine());
            Console.Write("b = ");
            b = Convert.ToInt32(Console.ReadLine());
            swap(ref a, ref b);
            Console.WriteLine("Po zamianie a = {0}, b = {1}", a, b);
            Console.ReadKey();
        }

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.