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

看板C_and_CPP作者Hazukashiine (みなさん、こんにちは)時間8年前 (2017/11/26 13:38)推噓12(12推 0噓 5→)

留言17則, 14人參與討論串3/3 (看更多)

這樣的寫法要追朔到手工撰寫組合語言當時連對記憶體和暫存器的使用都斤斤計較所以如果用一個額外的暫存器去儲存值的話代表 register spilling 的可能性會增加因為為了要確保這個跳到 label 處理完後要把我們剛 push 出去的值再 pop 回來要不少的時間這段時間是有點久故也被稱為 von Neumann bottleneck 用來描述資料在匯流排上的傳輸瓶頸 --- 題外話 --- 說到 XOR 的神奇技巧我們更常用的，甚至到現今都有在用的是：使用 XOR REG, REG 來把一個暫存器的值清零這樣做是確實會比 MOV 指令來得好現今的 CPU 為了拉高時脈跟吞吐量通常都把處理器做成管線式的 (pipelined) 這樣以來常常需要去處理 data hazard 因此 MOV 指令可能觸發 partial register stall 這跟指令的順序有很大的關係因此在 Intel 的規格書上有明確指出希望用 XOR 還有另外五種指令來清零 Intel 把它稱作 zero idioms 這些指令已經被 hard-coded 在晶片上讓處理器明確知道這個指令只是要清零而不會觸發額外的事件這樣可能會在一些關鍵的時刻提升效率 --- 結尾語 --- 無論如何在編譯器很聰明的年代把 code 寫得好懂真的比較實際甚至還更好優化寫了 XOR SWAP 一定一定比較慢因為 x86 提供 XCHG 來交換暫存器的值如果用一般的寫法（宣告額外的變數）優化器很容易優化你的程式碼挑選出這顆處理器最適當的指令出來所以說 Premature optimization is evil. 在沒確定這是效能瓶頸前過早進行一些優化可能會適得其反 ※ 引述《ptt0720 (濕濕)》之銘言： : 語言：CPP : 今天寫quick sort的時候發現原本常用的交數值方法好像有觀念上的問題 : https://i.imgur.com/GwH4NbM.png

: 我習慣的用法是第二十七行直接用參考交換兩個值 : 但是發現印出來後都是一堆0 : 後來交叉比對後發現是XOR交換值的問題 : 想請問一下是不是陣列用XOR交換數值會出錯？ : 想請問一下原因麻煩各位大大了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.185.23 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1511674682.A.71C.html ※ 編輯: Hazukashiine (61.230.0.89), 11/26/2017 13:47:07

推

alan23273850

11/26 13:57, 8年前 , 1^F

11/26 13:57, 1^F

推

galic

11/26 14:12, 8年前 , 2^F

11/26 14:12, 2^F

→

galic

11/26 14:12, 8年前 , 3^F

11/26 14:12, 3^F