{"id":537,"date":"2013-01-06T00:37:31","date_gmt":"2013-01-05T22:37:31","guid":{"rendered":"http:\/\/elwin013.com\/blog\/?p=537"},"modified":"2015-04-03T19:16:45","modified_gmt":"2015-04-03T18:16:45","slug":"zamiana-wartosci-zmiennych-bez-uzycia-zmiennej-pomocniczej","status":"publish","type":"post","link":"https:\/\/elwin013.com\/blog\/2013\/01\/zamiana-wartosci-zmiennych-bez-uzycia-zmiennej-pomocniczej\/","title":{"rendered":"Zamiana warto\u015bci zmiennych bez u\u017cycia zmiennej pomocniczej"},"content":{"rendered":"

\"BlogJednym z plus\u00f3w bycia studentem jest mo\u017cliwo\u015b\u0107 uczestniczenia w wielu r\u00f3\u017cnego typu wydarzeniach. Jak do tej pory na WAT<\/abbr> mia\u0142em okazje by\u0107 na ITAD<\/abbr> organizowanym przez CyberGuru<\/a> oraz na Samsung Open Day. I na tym drugim, a dok\u0142adniej na konkursowym zadaniu, kt\u00f3rego rozwi\u0105zanie uprawnia\u0142o do uczestnictwa w losowaniu telefonu oraz kilku innych, ju\u017c mniej ciekawych, nagr\u00f3d, chcia\u0142bym si\u0119 skupi\u0107. ;-)
\n
\nZadanie to brzmia\u0142o (w wielkim skr\u00f3cie) „Jak zamieni\u0107 miejscami warto\u015bci zmiennych, nie korzystaj\u0105c ze zmiennej pomocniczej”. Pomimo prostej tre\u015bci zadanie jest do\u015b\u0107 interesuj\u0105ce. W nowoczesnych j\u0119zykach wysokiego poziomu (jak na przyk\u0142ad Ruby, Perl, Python), zamiana mo\u017ce zosta\u0107 wykonana w jednej linii kodu (np. a, b = b, a<\/code>), co jednak nie uda si\u0119 w przypadku C, C++ czy Pascala. Z pomoc\u0105 przychodzi nam jednak funkcja logiczna XOR.<\/p>\n

Co to jest XOR?<\/h3>\n

XOR, czyli alternatywa wykluczaj\u0105ca, jest to (cytuj\u0105c za Wikipedi\u0105):<\/p>\n

Logiczny funktor zdaniotw\u00f3rczy (dwuargumentowa funkcja boolowska). R\u00f3\u017cnica symetryczna zda\u0144 jest prawdziwa wtedy i tylko wtedy, gdy dok\u0142adnie jedno ze zda\u0144 jest prawdziwe
\n\u0179r\u00f3d\u0142o: Alternatywa wykluczaj\u0105ca – Wikipedia<\/a><\/p><\/blockquote>\n

Ale co to znaczy? Znaczy to tylko tyle, \u017ce owa funkcja zwraca warto\u015b\u0107 „1” wtedy i tylko wtedy gdy dok\u0142adnie jeden z nich ma warto\u015b\u0107 logiczn\u0105 prawda, czyli „1”. Bardzo dobrze obrazuje to tablica prawdy (dost\u0119pna mi\u0119dzy innymi w artykule na Wikipedii), ale r\u00f3wnie dobrze mo\u017cna to pokaza\u0107 na przyk\u0142adzie:
\n<\/p>\n

     0101 = 5\r\nXOR  1001 = 9 \r\n---------\r\n     1100 = 12 <\/pre>\n
<\/code>
\nMamy dwie liczby – 5 oraz 9, na kt\u00f3rych chcemy bit po bicie wykona\u0107 alternatyw\u0119 wykluczaj\u0105c\u0105. I tak kolejno id\u0105c od strony najbardziej znacz\u0105cych bit\u00f3w (czyli od lewej strony) – 0 XOR 1 = 1, 1 XOR 0 = 1, 0 XOR 0 = 0, 1 XOR 1 = 0<\/code>, w efekcie daje nam to now\u0105 liczb\u0119 – 12. Co jednak stanie si\u0119 gdy wykonamy 12 XOR 5?
\n<\/p>\n
     1100 = 12\r\nXOR  0101 = 5\r\n---------\r\n     1001 = 9 <\/pre>\n
<\/code>
\nJak wida\u0107 otrzymamy z powrotem drug\u0105 liczb\u0119, czyli 9. Czyli je\u015bli zrobimy XOR dw\u00f3ch liczb, a nast\u0119pnie ten XOR tego wyniku i jednej z tych liczb to otrzymamy drug\u0105 liczb\u0119. Ta w\u0142asno\u015b\u0107 przyda nam si\u0119 w rozwi\u0105zaniu naszego zadania. :-)<\/p>\n
Rozwi\u0105zanie zadania<\/h3>\n
Jak ju\u017c wiemy jak dzia\u0142a XOR to rozwi\u0105zanie zadania staje si\u0119 proste. Za\u0142\u00f3\u017cmy, \u017ce mamy liczby a = 5 (0101b)<\/code> oraz b = 9 (1001b)<\/code> i chcemy je zamieni\u0107 miejscami. Je\u015bli wykonamy a XOR b<\/code> to w wyniku otrzymamy 12 (1100b)<\/code>. Teraz by otrzyma\u0107 jedn\u0105 z liczb wystarczy wykona\u0107 XOR wyniku oraz drugiej liczby. Czyli, aby zamieni\u0107 warto\u015bci zmiennych miejscami, wystarczy wykona\u0107 trzy operacje:
\n<\/p>\n
a = a XOR b \/\/ a = 5 XOR 9 = 12\r\nb = a XOR b \/\/ b = 12 XOR 9 = 5\r\na = a XOR b \/\/ a = 12 XOR 5 = 9<\/pre>\n
<\/code>
\nCo mo\u017cemy zapisa\u0107 nast\u0119puj\u0105co w j\u0119zyku C (oraz C++), wiedz\u0105c, \u017ce operatorem bitowym XOR jest tam ^<\/code>:
\n<\/p>\n
#include <stdio.h>\r\n\r\nmain() {\r\n  int a = 5, b = 9;\r\n  printf(\"a = %d, b = %d\\n\",a,b); \/\/ a = 5, b = 9\r\n  a=a^b;\r\n  b=a^b;\r\n  a=a^b;\r\n  printf(\"a = %d, b = %d\\n\",a,b); \/\/ a = 9, b = 5\r\n  return 0;\r\n}\r\n<\/pre>\n
<\/code>
\nJak wida\u0107 rozwi\u0105zanie zadania jest bardzo proste, je\u015bli tylko znamy „magiczne” w\u0142a\u015bciwo\u015bci operacji bitowych. I to by by\u0142o na tyle. Je\u015bli kto\u015b mia\u0142by inny pomys\u0142, rozwi\u0105zanie (a pewnie jeszcze przynajmniej jedno jest) to ch\u0119tnie pos\u0142ucham, a raczej przeczytam. ;-)<\/p>\n","protected":false},"excerpt":{"rendered":"
Jednym z plus\u00f3w bycia studentem jest mo\u017cliwo\u015b\u0107 uczestniczenia w wielu r\u00f3\u017cnego typu wydarzeniach. Jak do tej pory na WAT mia\u0142em okazje by\u0107 na ITAD organizowanym przez CyberGuru oraz na Samsung Open Day. I na tym drugim, a dok\u0142adniej na konkursowym zadaniu, kt\u00f3rego rozwi\u0105zanie uprawnia\u0142o do uczestnictwa w losowaniu telefonu oraz kilku innych, ju\u017c mniej ciekawych, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[29],"tags":[68,85,67],"class_list":["post-537","post","type-post","status-publish","format-standard","hentry","category-programowanie","tag-c","tag-programowanie","tag-xor"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t