[問題] 一種比較整數大小的寫法

[flax00298 (NI)]

int imin(int x, int y)
{

int mask = (x-y) >> (sizeof(int)*8-1);

return (x&mask) + (y&(~mask));

}


這是我在看別人寫的CODE的時候看到的

但是我一直看不懂為麼可以這樣寫

有麻煩知道的人可以解釋一下嗎??

謝謝

另外阿

用這樣的寫法有比直接用個if-else判斷還要好嗎?


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.233.149.115
※ 編輯: flax00298       來自: 125.233.149.115      (08/06 11:25)
推 ckclark:x >= y -> mask = 0, x < y -> mask = -1 (1111...1b)
推 jlovet:完全不會比較快
推 tomnelson:這種寫法只是要避免產生branch分支而已,不會比較快!
推 VictorTom:難懂, 推測就是為了不用branch所以特意這樣寫的吧...Orz
→ VictorTom:慢兩拍, 被樓上先推了....Q_Q~
→ firose:看不懂 ><
→ MOONRAKER:什麼branch？阻止CPU內branch prediction的運作嗎？
推 buganini:if-else的branch吧?  有到CPU裡面拿~摸深嗎?
推 tomnelson:補充:所謂branch分支就是組語裡的JMP/JNE/Jxx的指令!
→ MOONRAKER:那為何要阻止if的branch發生？還是阻止compiler最佳化？
→ tomnelson:上面的寫法翻成組語(assembly language)後,不會有J系列
→ tomnelson:指令產生,這樣CPU就不會在這段程式碼上去預測分支狀況!
推 VictorTom:就是單純避免conditional jump發生吧, 不然分支預測錯
→ VictorTom:誤, 要CPU pipeline重來一遍, 不過這東西是不是整個程式
→ VictorTom:的瓶頸, 搞到要寫這種比較不容易懂的程式, 就不清楚了:)
推 tomnelson:推VictorTom所說的! 不過這種寫法跟原先if-else比較起來
→ tomnelson:真的沒有比較快,不過在一些特殊場合倒是只能用這種寫法,
→ tomnelson:至於是哪些場合,我看待神人指教了! 哈~
推 ledia:如果某 jump 的 cost 特別高, 可能會有用吧
→ ledia:只是現在不知道有沒有這種 case
推 suhorng:我們說 signed int 的最高一位可以當 "符號" 位數
→ suhorng:所以 x-y < 0 的話 (x-y)&0x8000000 = 1 否則為 0
→ suhorng:那麼為什麼要 sizeof(int)*8 - 1 呢 ?
→ suhorng:他是配合 ">>" 右移運算子使用的
→ suhorng:sizeof(int)*8 是求出 int 總共有幾個 bit
→ suhorng:把 (x - y) 右移 (int的bit數 - 1) 之後就只剩下 sign bit
→ suhorng:因為 ">>" 運算子對有號數來說 若最高位是 "1" 則右移後左
推 sunneo:gpgpu正好有例子符合這種case
→ suhorng:邊補 1，否則補 0，因此若 x-y < 0 則 mask = -1 否則
→ suhorng:mask = 0 因此最後可以用 (x&mask) + (y&(~mask)) 傳回min
→ suhorng:對了 >>好像是sar指令 ?
推 softwind:X^=Y^=X^=Y 不是比較帥...
→ softwind:這種方式的code在 ARM系列的asm上應該不錯用每個指令
→ softwind:都可以check CPU status flagY
推 VictorTom:X^=Y^=X^=Y; 不是用來swap X Y用的嗎?_? 話說小弟有一次
→ VictorTom:好像sort一個array還是怎樣, 沒寫好讓同樣的array[i]做
→ VictorTom:swap, 一般temp變數不會怎樣, 用xor這招就換爛了....Orz
推 Chevelle:嗯.. 從 80386 (1985) 就開始說要用 SETxx 取代 Jxx 了