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 ${\displaystyle \otimes }$ oznacza XOR):

• L1. Przemienność: ${\displaystyle A\otimes B=B\otimes A}$
• L2. Łączność: ${\displaystyle (A\otimes B)\otimes C=A\otimes (B\otimes C)}$
• L3. Istnieje element neutralny: istnieje wartość ${\displaystyle Z=0}$ taka, że ${\displaystyle A\otimes Z=A}$ dla każdego ${\displaystyle A}$
• L4. Każdy element ma element odwrotny: dla każdego ${\displaystyle A,}$ istnieje ${\displaystyle A^{-\!1}}$ takie, że ${\displaystyle A\otimes A^{-\!1}=Z}$
  • L4a. Co więcej, każdy element jest swoim elementem odwrotnym: ${\displaystyle 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^[1] istnieje specjalny operator wymiany wartości. Dostępny jest w dwóch wariantach.

Operatory wymiany wartości w języku Icon^[1]

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

Przypisy

1. Ralph E. Griswold, Madge T. Griswold: Icon. Warszawa: Wydawnictwa Naukowo-Techniczne, 1987, seria: Biblioteka Inżynierii Oprogramowania. ISBN 83-204-0871-7. (pol.). Brak numerów stron w książce