作者ptt0720 (濕濕)
看板C_and_CPP
標題Re: [問題] XOR交換值問題
時間Thu Nov 23 15:19:28 2017
※ 引述《ptt0720 (濕濕)》之銘言：
: 語言：CPP
: 今天寫quick sort的時候發現原本常用的交數值方法好像有觀念上的問題
: https://i.imgur.com/GwH4NbM.png
: 我習慣的用法是第二十七行 直接用參考交換兩個值
: 但是發現印出來後都是一堆0
:
我簡單歸納一下討論結果 如有不對請再補充
XOR拿來交換是可以的 但是如果要換陣列的元素 記憶體位置不能一樣
如果 a = 0x0001 value = 3
b = 0x0001 value = 3
經過一次XOR之後 0x0001 ^ 0x0001 結果會是 0x0001 --> 0
可是此時 b記憶體位置也是0x0001 所以都是0
此時再討論下去已經無意義了
--
Talk is cheap. Show me the code. - Torvalds, Linus (2000-08-25).
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 163.22.18.105
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1511421582.A.9DD.html
1F：→ galic: you got it 11/23 15:56
2F：→ ptt0720: 謝謝大大 11/23 16:16
3F：推 alan23273850: 推 11/23 19:05
4F：→ tcn1john: 新手發問: 請問陣列記憶體位置互換會有效能問題嗎？ 11/23 20:39
5F：→ jerryh001: 陣列的元素"位置"不是可以交換的東西 11/23 20:43
6F：推 tcn1john: 弄懂了...是直接寫入，不是互換位置，感謝回覆 11/23 20:44
7F：推 CaptainH: xor交換其實是比正常swap慢的 11/24 10:18
8F：→ CaptainH: 因為正常swap只要三次賦值，xor交換還有額外三次xor運 11/24 10:19
9F：→ CaptainH: 算 11/24 10:19
10F：推 CaptainH: 總之是語義有歧義,執行有風險,無法一般化,速度反而慢 11/24 10:22
11F：→ CaptainH: 的做法 11/24 10:22
12F：推 alan23273850: 所以沒事不要用奇技淫巧 11/24 10:44
13F：→ galic: 但從pipeline CPU角度來看 Execute跟Write-back本來就不同 11/24 11:16
14F：→ galic: stage 所以樓上C大說的理由不太完整.... 11/24 11:16
15F：→ galic: 以前的ISA是真的有特殊理由去刻意使用XOR，但這都是歷史了 11/24 11:17
16F：→ galic: 從現在的角度來看 XOR Swap的缺點主要是 可讀性 以及編譯器 11/24 11:17
17F：→ galic: 是否能理解XOR Swap，然後優化成合適的指令 11/24 11:17
18F：→ galic: 然後提一下，從計組的觀點，目前XOR Swap的缺點應該是 11/24 11:18
19F：→ galic: XOR必須經過運算才能得知結果 這會影響硬體能做的優化 11/24 11:19
20F：→ galic: 像是Branch Prediciton和Speculative Excution之類的 11/24 11:21
21F：→ galic: 所以這年頭使用適當的演算法跟資料結構 其他交給編譯器就好 11/24 11:26
22F：→ Lipraxde: 這樣換就省了點RAM看起來帥而已 11/24 13:39