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

作者: ptt0720 (濕濕)   2017-11-23 15:19:28
※ 引述《ptt0720 (濕濕)》之銘言:
: 語言:CPP
: 今天寫quick sort的時候發現原本常用的交數值方法好像有觀念上的問題
: https://i.imgur.com/GwH4NbM.png
: 我習慣的用法是第二十七行 直接用參考交換兩個值
: 但是發現印出來後都是一堆0
:
我簡單歸納一下討論結果 如有不對請再補充
XOR拿來交換是可以的 但是如果要換陣列的元素 記憶體位置不能一樣
如果 a = 0x0001 value = 3
b = 0x0001 value = 3
經過一次XOR之後 0x0001 ^ 0x0001 結果會是 0x0001
作者: galic (嘎利)   2017-11-23 15:56:00
you got it
作者: ptt0720 (濕濕)   2017-11-23 16:16:00
謝謝大大
作者: alan23273850   2017-11-23 19:05:00
作者: tcn1john (momo)   2017-11-23 20:39:00
新手發問: 請問陣列記憶體位置互換會有效能問題嗎?
作者: jerryh001   2017-11-23 20:43:00
陣列的元素"位置"不是可以交換的東西
作者: tcn1john (momo)   2017-11-23 20:44:00
弄懂了...是直接寫入,不是互換位置,感謝回覆
作者: CaptainH (Cannon)   2017-11-24 10:18:00
xor交換其實是比正常swap慢的因為正常swap只要三次賦值,xor交換還有額外三次xor運算總之是語義有歧義,執行有風險,無法一般化,速度反而慢的做法
作者: alan23273850   2017-11-24 10:44:00
所以沒事不要用奇技淫巧
作者: galic (嘎利)   2017-11-24 11:16:00
但從pipeline CPU角度來看 Execute跟Write-back本來就不同stage 所以樓上C大說的理由不太完整....以前的ISA是真的有特殊理由去刻意使用XOR,但這都是歷史了從現在的角度來看 XOR Swap的缺點主要是 可讀性 以及編譯器是否能理解XOR Swap,然後優化成合適的指令然後提一下,從計組的觀點,目前XOR Swap的缺點應該是XOR必須經過運算才能得知結果 這會影響硬體能做的優化像是Branch Prediciton和Speculative Excution之類的所以這年頭使用適當的演算法跟資料結構 其他交給編譯器就好
作者: Lipraxde (Lipraxde)   2017-11-24 13:39:00
這樣換就省了點RAM看起來帥而已

Links booklink

Contact Us: admin [ a t ] ucptt.com