Zamiana wartości zmiennych

Z Wikipedii

W informatyce często zachodzi potrzeba zamiany wartości dwóch zmiennych (ang. swap).

Standardowy, prawie zawsze używany algorytm zamiany wymaga chwilowego kopiowania jednej ze zmiennych:

 funkcja swap(zmienna a, zmienna b)
 {
        zmienna c:=a;
        a:=b;
        b:=c;
 }

Możliwa jest także zamiana zmiennych bez użycia tymczasowej zmiennej.

[edytuj] Zamiana za pomocą dodawania i odejmowania

Zamiana wartości zmiennych integer bez dodatkowej zmiennej tymczasowej, za pomocą dodawania i odejmowania:

funkcja swap(integer a, integer b)
{
        a:=a+b;
        b:=a-b;
        a:=a-b;
}

Algorytm ten nie działa na systemach sprawdzających przekroczenia zakresu liczb całkowitych (ang. integer overflow).

[edytuj] Zamiana za pomocą operacji XOR

Zamianę wartości zmiennych można także zrealizować za pomocą operacji XOR:

funkcja swap(integer a, integer b)
{
        a := a XOR b
        b := a XOR b
        a := a XOR b
}

W tym algorytmie nie dochodzi do przekraczania zakresu liczb całkowitych, ani nie jest wymagana zmienna tymczasowa. Na współczesnych procesorach jest jednak zbyt wolny. Używa się go w niektórych systemach wbudowanych, gdzie ilość dostępnego miejsca dla zmiennych jest bardzo ograniczona.

[edytuj] Dowód

Działanie binarne XOR na maskach bitowych ma następujące własności (gdzie $\otimes$ oznacza XOR):

L1. Przemienność: $A \otimes B = B \otimes A$
L2. Łączność: $(A \otimes B) \otimes C = A \otimes (B \otimes C)$
L3. Istnieje element neutralny: istnieje wartość $Z = 0$ taka, że $A \otimes Z = A$ dla każdego $A$
L4. Każdy element ma element odwrotny: dla każdego A, istnieje takie, że
- L4a. Co więcej, każdy element jest swoim elementem odwrotnym: $A \otimes A = 0$ .

Pierwsze cztery właściwości to definicja grupy abelowej. Ostatnia to własność XOR nie koniecznie występująca w innych grupach abelowych, czy grupach w ogóle.

Załóżmy, że mamy dwa rejestry R1 i R2, jak w tabeli poniżej, z początkowymi wartościami odpowiednio A i B. Wykonujemy kolejno operacje i redukujemy wyniki za pomocą powyższej listy własności.

Krok	Działanie	Rejestr 1	Rejestr 2	Redukcja
1	Wartość początkowa	A	B	—
2	`R1 := R1 ^ R2`	A^B	B	—
3	`R2 := R1 ^ R2`	A^B = B^A	(A^B)^B = A^(B^B) = A^0 = A	L1, L2, L4, L3
4	`R1 := R1 ^ R2`	(B^A)^A = B^(A^A) = B^0 = B	A	L2, L3, L4