Zamiana wartości zmiennych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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. 1,0 1,1 Ralph E. Griswold, Madge T. Griswold: Icon. Warszawa: Wydawnictwa Naukowo-Techniczne, 1987, seria: Biblioteka Inżynierii Oprogramowania. ISBN ISBN 83-204-0871-7. (pol.)