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

看板C_and_CPP作者 (NI)時間15年前 (2009/08/06 11:23), 編輯推噓14(14推 0噓 24→)
留言38則, 12人參與, 最新討論串1/1
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)
推
08/06 11:46, , 1F
x >= y -> mask = 0, x < y -> mask = -1 (1111...1b)
08/06 11:46, 1F
推
08/06 11:50, , 2F
完全不會比較快
08/06 11:50, 2F
推
08/06 11:58, , 3F
這種寫法只是要避免產生branch分支而已,不會比較快!
08/06 11:58, 3F
推
08/06 12:00, , 4F
難懂, 推測就是為了不用branch所以特意這樣寫的吧...Orz
08/06 12:00, 4F
→
08/06 12:01, , 5F
慢兩拍, 被樓上先推了....Q_Q~
08/06 12:01, 5F
→
08/06 12:34, , 6F
看不懂 ><
08/06 12:34, 6F
→
08/06 12:40, , 7F
什麼branch？阻止CPU內branch prediction的運作嗎？
08/06 12:40, 7F
推
08/06 12:52, , 8F
if-else的branch吧? 有到CPU裡面拿~摸深嗎?
08/06 12:52, 8F
推
08/06 13:58, , 9F
補充:所謂branch分支就是組語裡的JMP/JNE/Jxx的指令!
08/06 13:58, 9F
→
08/06 13:58, , 10F
那為何要阻止if的branch發生？還是阻止compiler最佳化？
08/06 13:58, 10F
→
08/06 13:58, , 11F
上面的寫法翻成組語(assembly language)後,不會有J系列
08/06 13:58, 11F
→
08/06 14:00, , 12F
指令產生,這樣CPU就不會在這段程式碼上去預測分支狀況!
08/06 14:00, 12F
推
08/06 14:00, , 13F
就是單純避免conditional jump發生吧, 不然分支預測錯
08/06 14:00, 13F
→
08/06 14:01, , 14F
誤, 要CPU pipeline重來一遍, 不過這東西是不是整個程式
08/06 14:01, 14F
→
08/06 14:02, , 15F
的瓶頸, 搞到要寫這種比較不容易懂的程式, 就不清楚了:)
08/06 14:02, 15F
推
08/06 14:07, , 16F
推VictorTom所說的! 不過這種寫法跟原先if-else比較起來
08/06 14:07, 16F
→
08/06 14:09, , 17F
真的沒有比較快,不過在一些特殊場合倒是只能用這種寫法,
08/06 14:09, 17F
→
08/06 14:09, , 18F
至於是哪些場合,我看待神人指教了! 哈~
08/06 14:09, 18F
推
08/06 14:39, , 19F
如果某 jump 的 cost 特別高, 可能會有用吧
08/06 14:39, 19F
→
08/06 14:39, , 20F
只是現在不知道有沒有這種 case
08/06 14:39, 20F
推
08/06 22:04, , 21F
我們說 signed int 的最高一位可以當 "符號" 位數
08/06 22:04, 21F
→
08/06 22:05, , 22F
所以 x-y < 0 的話 (x-y)&0x8000000 = 1 否則為 0
08/06 22:05, 22F
→
08/06 22:05, , 23F
那麼為什麼要 sizeof(int)*8 - 1 呢 ?
08/06 22:05, 23F
→
08/06 22:05, , 24F
他是配合 ">>" 右移運算子使用的
08/06 22:05, 24F
→
08/06 22:06, , 25F
sizeof(int)*8 是求出 int 總共有幾個 bit
08/06 22:06, 25F
→
08/06 22:07, , 26F
把 (x - y) 右移 (int的bit數 - 1) 之後就只剩下 sign bit
08/06 22:07, 26F
→
08/06 22:07, , 27F
因為 ">>" 運算子對有號數來說 若最高位是 "1" 則右移後左
08/06 22:07, 27F
推
08/06 22:08, , 28F
gpgpu正好有例子符合這種case
08/06 22:08, 28F
→
08/06 22:08, , 29F
邊補 1，否則補 0，因此若 x-y < 0 則 mask = -1 否則
08/06 22:08, 29F
→
08/06 22:08, , 30F
mask = 0 因此最後可以用 (x&mask) + (y&(~mask)) 傳回min
08/06 22:08, 30F
→
08/06 22:09, , 31F
對了 >>好像是sar指令 ?
08/06 22:09, 31F
推
08/07 01:11, , 32F
X^=Y^=X^=Y 不是比較帥...
08/07 01:11, 32F
→
08/07 01:12, , 33F
這種方式的code在 ARM系列的asm上應該不錯用每個指令
08/07 01:12, 33F
→
08/07 01:12, , 34F
都可以check CPU status flagY
08/07 01:12, 34F
推
08/07 01:25, , 35F
X^=Y^=X^=Y; 不是用來swap X Y用的嗎?_? 話說小弟有一次
08/07 01:25, 35F
→
08/07 01:26, , 36F
好像sort一個array還是怎樣, 沒寫好讓同樣的array[i]做
08/07 01:26, 36F
→
08/07 01:27, , 37F
swap, 一般temp變數不會怎樣, 用xor這招就換爛了....Orz
08/07 01:27, 37F
推
08/07 13:19, , 38F
嗯.. 從 80386 (1985) 就開始說要用 SETxx 取代 Jxx 了
08/07 13:19, 38F
‣ 更多 flax00298 的文章
文章代碼(AID): #1AUao_OM (C_and_CPP)