※ 引述《timecrisis (........)》之銘言:
: : 推 mmss33:其實這是很基本的東西喔 ^^" http://0rz.net/fe1va 06/27 14:36
: : → mmss33:http://0rz.net/9a1yo 06/27 14:37
: void swap(int *a, int *b)
: {
: *a = *a ^ *b;
: *b = *b ^ *a;
: *a = *a ^ *b;
: }
: 在裡面 ^ 代表什麼意義嗎?
: 用法是什麼呢?
: 還有裡面提到的 xor 是C++的嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.75.178.1
> -------------------------------------------------------------------------- <
作者: sjgau (sjgau) 看板: C_and_CPP
標題: Re: [問題] 請教如何只用x,y兩變數來交換彼此數值
時間: Mon Apr 11 14:09:42 2011
int a, b;
a= 123; b= 456;
a^= b^= a^= b;
// 只要 一行指令,不需要使用第三個變數,
即可達到 目的。
請問:為什麼?
※ 引述《ballgi (環給一個幸福)》之銘言:
: 不好意思,我想請教一個問題
: x=1
: y=2
: 如果不用第三個變數就能轉換彼此的數值為
: x=2
: y=1
: 我不知道可以這樣作耶,請問誰能指導我,謝謝
: 在此感謝鄉民提供的智慧
> -------------------------------------------------------------------------- <
作者: yauhh (喲) 看板: C_and_CPP
標題: Re: [問題] 請教如何只用x,y兩變數來交換彼此數值
時間: Mon Apr 11 20:53:48 2011
※ 引述《sjgau (sjgau)》之銘言:
: int a, b;
: a= 123; b= 456;
: a^= b^= a^= b;
: // 只要 一行指令,不需要使用第三個變數,
: 即可達到 目的。
: 請問:為什麼?
: ※ 引述《ballgi (環給一個幸福)》之銘言:
: : 不好意思,我想請教一個問題
: : x=1
: : y=2
: : 如果不用第三個變數就能轉換彼此的數值為
: : x=2
: : y=1
: : 我不知道可以這樣作耶,請問誰能指導我,謝謝
: : 在此感謝鄉民提供的智慧
當 a == b 時, a ^ b ===> 0, 會把這局破掉.
所以起碼應該寫成:
a == b? 1 : (a ^= b ^= a ^= b);
> -------------------------------------------------------------------------- <
作者: LPH66 (-858993460) 看板: C_and_CPP
標題: Re: [問題] 請教如何只用x,y兩變數來交換彼此數值
時間: Mon Apr 11 23:40:29 2011
: → littleshan:不要這樣寫!這是 implementation-defined behavior 04/11 15:48
: → littleshan:就是十誡之八啦 04/11 15:49
基本上這個寫法的確是 implementation-defined behavior
不管有沒有加括號都一樣
事情是這樣的
a ^= b ^= a ^= b;
1 2 3 4 5 6 7
這樣寫的人想要做的事的順序是
值為
(7) 取 b 的值 原來的 b
(5) 取 a 的值 原來的 a
(6) 做 (5)^(7) 並把值放回 a 去 原來的 a^b
(3) 取 b 的值 原來的 b
(4) 做 (3)^(6) 並把值放回 b 去 原來的 a
(1) 取 a 的值 原來的 a^b
(2) 做 (1)^(4) 並把值放回 a 去 原來的 b
但有些 compiler (如我手上的 g++ 4.1.0 for win) 會編成這個順序
值為
(1) 取 a 的值 原來的 a
(3) 取 b 的值 原來的 b
(5) 取 a 的值 原來的 a
(7) 取 b 的值 原來的 b
(6) 做 (5)^(7) 並把值放回 a 去 原來的 a^b
(4) 做 (3)^(6) 並把值放回 b 去 原來的 a
(2) 做 (1)^(4) 並把值放回 a 去 一定是 0
結果是原來 a 的值在 b 但 a 卻變成 0 了
問題在於
雖然這個式子的確是分析成
^= (2)
/ \
a ^= (4)
(1) / \
b ^= (6)
(3) / \
a b
(5) (7)
這個樣子 但在計算 a ^= b 時 a b 取值的順序卻是 implementation-defined
也就是在上面那棵語法樹的後序走訪中先走左子樹還是先走右子樹
如果先走左子樹 就是 1 3 5 7 6 4 2 的順序
先走右子樹 就是 7 5 6 3 4 1 2 的順序
而這兩個順序 上面我也寫出來了
後者是順利交換沒錯 前者卻是把 a 搬到 b 後把 a 炸成 0 !
所以結論是千萬不要用這個寫法
---
其實簡單一句話就是十三誡之八裡說的
你不可以在一個運算式(expression)中,對一個基本型態的變數修改其值
超過一次以上。否則,將導致未定義的行為(undefined behavior)
如果真要用 xor 來交換 乖乖寫三條
x ^= y; y ^= x; x ^= y;
就什麼事都沒有....
當然最好的寫法還是 int temp = x; x = y; y = temp; 就是了
這是一種交換兩個數值的快速運算法則!
你可以將A和B分別帶入兩個不同的數值試試看,你就會看到有什麼樣的情況產生了!
基本的理論是將兩個數值做三次的XOR的位元運算,
就能得到兩個數值交換的結果!
這在有一本書中有提到,
書名為Programming Interview Exposed,
John Wiley & Sons出版
裡面介紹許多罕見卻好用的程式技巧,
歡迎大家去參考看看!