Re: [問題] XOR交換值問題

看板C_and_CPP作者 (濕濕)時間6年前 (2017/11/23 15:19), 編輯推噓5(5017)
留言22則, 7人參與, 6年前最新討論串2/3 (看更多)
※ 引述《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://www.ptt.cc/bbs/C_and_CPP/M.1511421582.A.9DD.html

11/23 15:56, 6年前 , 1F
you got it
11/23 15:56, 1F

11/23 16:16, 6年前 , 2F
謝謝大大
11/23 16:16, 2F

11/23 19:05, 6年前 , 3F
11/23 19:05, 3F

11/23 20:39, 6年前 , 4F
新手發問: 請問陣列記憶體位置互換會有效能問題嗎?
11/23 20:39, 4F

11/23 20:43, 6年前 , 5F
陣列的元素"位置"不是可以交換的東西
11/23 20:43, 5F

11/23 20:44, 6年前 , 6F
弄懂了...是直接寫入,不是互換位置,感謝回覆
11/23 20:44, 6F

11/24 10:18, 6年前 , 7F
xor交換其實是比正常swap慢的
11/24 10:18, 7F

11/24 10:19, 6年前 , 8F
因為正常swap只要三次賦值,xor交換還有額外三次xor運
11/24 10:19, 8F

11/24 10:19, 6年前 , 9F
11/24 10:19, 9F

11/24 10:22, 6年前 , 10F
總之是語義有歧義,執行有風險,無法一般化,速度反而慢
11/24 10:22, 10F

11/24 10:22, 6年前 , 11F
的做法
11/24 10:22, 11F

11/24 10:44, 6年前 , 12F
所以沒事不要用奇技淫巧
11/24 10:44, 12F

11/24 11:16, 6年前 , 13F
但從pipeline CPU角度來看 Execute跟Write-back本來就不同
11/24 11:16, 13F

11/24 11:16, 6年前 , 14F
stage 所以樓上C大說的理由不太完整....
11/24 11:16, 14F

11/24 11:17, 6年前 , 15F
以前的ISA是真的有特殊理由去刻意使用XOR,但這都是歷史了
11/24 11:17, 15F

11/24 11:17, 6年前 , 16F
從現在的角度來看 XOR Swap的缺點主要是 可讀性 以及編譯器
11/24 11:17, 16F

11/24 11:17, 6年前 , 17F
是否能理解XOR Swap,然後優化成合適的指令
11/24 11:17, 17F

11/24 11:18, 6年前 , 18F
然後提一下,從計組的觀點,目前XOR Swap的缺點應該是
11/24 11:18, 18F

11/24 11:19, 6年前 , 19F
XOR必須經過運算才能得知結果 這會影響硬體能做的優化
11/24 11:19, 19F

11/24 11:21, 6年前 , 20F
像是Branch Prediciton和Speculative Excution之類的
11/24 11:21, 20F

11/24 11:26, 6年前 , 21F
所以這年頭使用適當的演算法跟資料結構 其他交給編譯器就好
11/24 11:26, 21F

11/24 13:39, 6年前 , 22F
這樣換就省了點RAM看起來帥而已
11/24 13:39, 22F
文章代碼(AID): #1Q5dQEdT (C_and_CPP)
討論串 (同標題文章)
文章代碼(AID): #1Q5dQEdT (C_and_CPP)