elwin013's blog

kawałek sieci młodego geeka

Cześć, jestem Kamil! Witaj na moim blogu!

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". ;-)

z głową w chmurach -

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"

Zostaw komentarz