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 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
Przypisy
Kategoria:Algorytmy