Re: [問題] 面試考題 程式最佳化
※ 引述《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)
推
06/16 00:31, , 1F
06/16 00:31, 1F
→
06/16 00:33, , 2F
06/16 00:33, 2F
→
06/16 00:34, , 3F
06/16 00:34, 3F
→
06/16 00:40, , 4F
06/16 00:40, 4F
推
06/16 01:08, , 5F
06/16 01:08, 5F
推
06/16 01:56, , 6F
06/16 01:56, 6F
已修正
追加個 IS_OVERFLOW
若會就不優化 不會就用上面的方法
※ 編輯: DrStein 來自: 58.115.132.79 (06/16 02:30)
討論串 (同標題文章)