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 oznacza XOR):
- L1. Przemienność:
- L2. Łączność:
- L3. Istnieje element neutralny: istnieje wartość taka, że dla każdego
- L4. Każdy element ma element odwrotny: dla każdego istnieje takie, że
- L4a. Co więcej, każdy element jest swoim elementem odwrotnym:
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.
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
- ↑ a b Ralph E. Griswold, Madge T. Griswold: Icon. Warszawa: Wydawnictwa Naukowo-Techniczne, 1987, seria: Biblioteka Inżynierii Oprogramowania. ISBN 83-204-0871-7. (pol.).