Zamiana wartości zmiennych bez użycia zmiennej pomocniczej
Jednym z plusów bycia studentem jest możliwość uczestniczenia w wielu różnego typu wydarzeniach. Jak do tej pory na WAT miałem okazje być na ITAD organizowanym przez CyberGuru oraz na Samsung Open Day. I na tym drugim, a dokładniej na konkursowym zadaniu, którego rozwiązanie uprawniało do uczestnictwa w losowaniu telefonu oraz kilku innych, już mniej ciekawych, nagród, chciałbym się skupić. ;-)
Zadanie to brzmiało (w wielkim skrócie) „Jak zamienić miejscami wartości zmiennych, nie korzystając ze zmiennej pomocniczej”. Pomimo prostej treści zadanie jest dość interesujące. W nowoczesnych językach wysokiego poziomu (jak na przykład Ruby, Perl, Python), zamiana może zostać wykonana w jednej linii kodu (np. a, b = b, a
), co jednak nie uda się w przypadku C, C++ czy Pascala. Z pomocą przychodzi nam jednak funkcja logiczna XOR.
Co to jest XOR?
XOR, czyli alternatywa wykluczająca, jest to (cytując za Wikipedią):
Logiczny funktor zdaniotwórczy (dwuargumentowa funkcja boolowska). Różnica symetryczna zdań jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jedno ze zdań jest prawdziwe
Źródło: Alternatywa wykluczająca – Wikipedia
Ale co to znaczy? Znaczy to tylko tyle, że owa funkcja zwraca wartość „1” wtedy i tylko wtedy gdy dokładnie jeden z nich ma wartość logiczną prawda, czyli „1”. Bardzo dobrze obrazuje to tablica prawdy (dostępna między innymi w artykule na Wikipedii), ale równie dobrze można to pokazać na przykładzie:
0101 = 5 XOR 1001 = 9 --------- 1100 = 12
Mamy dwie liczby – 5 oraz 9, na których chcemy bit po bicie wykonać alternatywę wykluczającą. I tak kolejno idąc od strony najbardziej znaczących bitów (czyli od lewej strony) – 0 XOR 1 = 1, 1 XOR 0 = 1, 0 XOR 0 = 0, 1 XOR 1 = 0
, w efekcie daje nam to nową liczbę – 12. Co jednak stanie się gdy wykonamy 12 XOR 5?
1100 = 12 XOR 0101 = 5 --------- 1001 = 9
Jak widać otrzymamy z powrotem drugą liczbę, czyli 9. Czyli jeśli zrobimy XOR dwóch liczb, a następnie ten XOR tego wyniku i jednej z tych liczb to otrzymamy drugą liczbę. Ta własność przyda nam się w rozwiązaniu naszego zadania. :-)
Rozwiązanie zadania
Jak już wiemy jak działa XOR to rozwiązanie zadania staje się proste. Załóżmy, że mamy liczby a = 5 (0101b)
oraz b = 9 (1001b)
i chcemy je zamienić miejscami. Jeśli wykonamy a XOR b
to w wyniku otrzymamy 12 (1100b)
. Teraz by otrzymać jedną z liczb wystarczy wykonać XOR wyniku oraz drugiej liczby. Czyli, aby zamienić wartości zmiennych miejscami, wystarczy wykonać trzy operacje:
a = a XOR b // a = 5 XOR 9 = 12 b = a XOR b // b = 12 XOR 9 = 5 a = a XOR b // a = 12 XOR 5 = 9
Co możemy zapisać następująco w języku C (oraz C++), wiedząc, że operatorem bitowym XOR jest tam ^
:
#include <stdio.h> main() { int a = 5, b = 9; printf("a = %d, b = %d\n",a,b); // a = 5, b = 9 a=a^b; b=a^b; a=a^b; printf("a = %d, b = %d\n",a,b); // a = 9, b = 5 return 0; }
Jak widać rozwiązanie zadania jest bardzo proste, jeśli tylko znamy „magiczne” właściwości operacji bitowych. I to by było na tyle. Jeśli ktoś miałby inny pomysł, rozwiązanie (a pewnie jeszcze przynajmniej jedno jest) to chętnie posłucham, a raczej przeczytam. ;-)
6 komentarzy do “Zamiana wartości zmiennych bez użycia zmiennej pomocniczej”
Podobnie możemy też zrobić: a = 5; b = 9 a = a + b // a = 5 + 9 = 14 b = a - b // b = 14 - 9 = 5 a = a - b // a = 14 - 5 = 9 Ale XOR jest lepszy, bo zdecydowanie szybszy niż operacje arytmetyczne. : )
O. I to jest to drugie rozwiązanie. Dzięki za podrzucenie :-) To fakt, XOR jest szybszy. I wygląda "bardziej profesjonalnie". ;-)
Programowanie,zawartość komputera i systemu operacyjnego, bla bla bla... zawsze były dla mnie światem tak odległym i pozornie nieosiągalnym. Obsługa, w moim przypadku ograniczała się do sprawdzenia poczty, zagrania w grę, wirtualne rozmowy, słuchanie muzyki etc etc. Ale mam nadzieję, że nie świadczy to o mojej ignorancji (choć ostatnio z własnej inicjatywy nauczyłam się formatować Windowsa). Ale mimo to, jako człowiek światły, żądny wiedzy, poszerzania swoich horyzontów i chęcią zaszpanowania przed znajomymi (ha! wiem co to XOR, a wy nie!) z chęcią będę wracać do tego miejsca w sieci. A to, że ktoś ma pasję i naprawdę go to kręci jest doprawdy imponujące. I ja się jaram! Pozdrawiam!
mój nauczyciell powtarza: "źrudło to nie jest wikipedia bo każdy może pisać tam co chce"
Faktycznie, powinno być "owa" a nie "ów" ;)
Zostaw komentarz