Zamiana wartości zmiennych

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.

Zamiana za pomocą dodawania i odejmowania

Zamiana wartości zmiennych typu liczba całkowita 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.

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.

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 $A^{-\!1}$ takie, że $A \otimes A^{-\!1} = Z$
  • 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 niekoniecznie 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

Zamiana za pomocą operatora list

Zamiana wartości zmiennych dowolnego typu bez dodatkowej zmiennej tymczasowej, za pomocą operatora list (w języku PHP):

list($a, $b) = array($b, $a);

podobnie dowolną liczbę zmiennych:

list($a, $b, $c, ...) = array(..., $c, $b, $a);

Operator zamiany wartości

W języku Icon istnieje specjalny operator wymiany wartości. Dostępny jest w dwóch wariantach.

Operatory wymiany wartości w języku Icon

operator	przykład kodu	działanie
:=:	a:=:b	wymiana wartości
<=>	a<=>b	wymiana wartości z możliwością odwrócenia przy wznowieniu