Re: [問題] 面試考題 程式最佳化

[DrStein (啤酒肚)]

※ 引述《apey ()》之銘言：
: hi
: 以下是我今天面試所遇到的考題, 來這裡請教大家
: a,b是 unsigned int
: 最佳化以下兩段程式碼 1 跟 2
: 1.if ( (a/24) > b ) return 1;

        更快的做法:

#define MUL24(XX)           (( (XX)<<4) + ( (XX)<<3) )
#define IS_NEGATIVE(XX)     (((XX)&(0x80000000)) >> 31)
#define IS_OVERFLOW(XX)     (((XX)&(0xf0000000)) >> 24)


        if( IS_NEGATIVE(a-MUL24(b) )
                return 1;

        共三個位移 一個加法 一個減法 一個位運算(&)，一個比較，一個跳越

        通常位移/位運算是耗1個時鍾，整數加/減/比較也是一個(over pentium 4)

        所以共是7個時鐘+跳越

        前提是下溢時就給他溢，這是x86的預設結果(可以關掉)


        未優化是 一個整數除法，一個整數比較 還有一個跳越

        整數除法會耗掉40-80個時鐘(依機器而定)

        所以加速了六倍以上。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 58.115.132.79
※ 編輯: DrStein         來自: 58.115.132.79        (06/16 00:08)
推 ilway25:並不等價，若b=0x80000000則判斷錯誤
→ ilway25:例子：a=b=0x80000000
→ ilway25:littleshan 那篇的作法就是要確保，在 任何情況 下都對
→ DrStein:不考率會溢位。。
推 LPH66:都考慮下溢了為什麼不考慮上溢...?
推 littleshan:就算不考慮溢位好了...你的MUL24寫錯囉 XD
        已修正

        追加個 IS_OVERFLOW

        若會就不優化 不會就用上面的方法
※ 編輯: DrStein         來自: 58.115.132.79        (06/16 02:30)