Pascal


Jak zamienić miejscami zawartość dwóch zmiennych...

      ... bez korzystania ze zmiennych pomocniczych?

Zamiana dwóch liczb przy pomocy jednej zmiennej pomocniczej nie jest trudna w realizacji. Okazuje się jednak, że można zamienić dwie liczby nie korzystając z żadnych dodatkowych zmiennych! W tym celu należy się posłużyć operacją XOR (alternatywa wyłączna).

Co to jest operacja XOR?

Na bitach można wykonywać operacje logiczne takie jak: AND (koniunkcja), OR (alternatywa), czy właśnie XOR. Polegają one na porównaniu poszczególnych bitów zadanych liczb i zwrócenie wyniku tego porównania:

1 AND 1 = 1
0 AND 1 = 0
1 AND 0 = 0
0 AND 0 = 0

1 OR 1 = 1
0 OR 1 = 1
1 OR 0 = 1
0 OR 0 = 0

Jak widać operacja AND jest prawdziwa wtedy, gdy oba bity maja wartość 1 (prawda), a OR jest prawdziwe gdy CONAJMNIEJ jeden bit ma wartość 1.

Co zatem zwraca XOR? XOR zwraca prawdę (czyli 1) gdy TYLKO JEDEN z porównywanych bitów ma wartość 1. A wiec:

1 XOR 1 = 0
0 XOR 1 = 1
1 XOR 0 = 1
0 XOR 0 = 0

Co więcej operacja XOR ma ciekawa własność. Mianowicie mamy dane dwie liczby A i B. Wtedy po operacji XOR dadzą one jakąś liczbę C: A XOR B = C (również B XOR A = C). Okazuje się, że wynikiem operacji XOR na liczbie C i jednej z tych liczb jest druga liczba:

C XOR A = B
C XOR B = A

Przykład praktyczny:

101 XOR 100 = 001
001 XOR 100 = 101
001 XOR 101 = 100

I ta własność jest wykorzystana przy zamianie liczb!

Aby dokonać tej zamiany wystarczy wykonać następujące działania (zamieniamy miejscami zawartość zmiennych A i B):

(1) A = A XOR B
(2) B = A XOR B
(3) A = A XOR B

Zobaczmy co dzieje się z zawartością zmiennych po tych operacjach:

(0) Załóżmy, że zmienna A zawiera liczbę o wartości x, a zmienna B zawiera liczbę o wartości y. Wiemy też, że A XOR B = z (x XOR y = z). Liczby z nie znamy ale tak naprawdę nie będzie nam to potrzebne.

Wartości zmiennych przed zamianą:

A = x
B = y

(1) Do zmiennej A przypisujemy A XOR B, a wiec x XOR y, co jest równe z.

Wartości zmiennych po 1 operacji:

A = z
B = y

(2) Teraz do zmiennej B zapisujemy wynik operacji A XOR B, a że w zmiennej A znajduje się już liczba z zostanie wykonana operacja z XOR y, z własności operacji XOR wiemy, że wynikiem będzie liczba x (z XOR y = x).

Wartości zmiennych po 2 operacji:

A = z
B = x

(3) Na koniec jeszcze raz XOR'ujemy liczby - A XOR B (z XOR x = y), wynikiem jest liczba y, którą przypisujemy do zmiennej A.

Wartości zmiennych po 3 operacji:

A = y
B = x

I tym samym zamieniliśmy ze sobą dwie liczby nie korzystając z żadnych innych zmiennych!

Dodał: ifrost​, www
Dział: Pascal


 

ComputerSun.pl na FaceBooku
Polecamy lekturę:

Windows 7 PL. Ćwiczenia praktyczne



X

Zapisz się na biuletyn serwisu ComputerSun.pl, aby otrzymać poradnik:

Zabezpieczanie sieci bezprzewodowych. Przydatne wskazówki jak chronić sieć domową przed intruzami

Imię:  
Email:
Tak, akceptuję Politykę Prywatności