高效的C編程之除法運(yùn)算

14.2 除法運(yùn)算
　　因?yàn)?a target='_blank' class='arckwlink_none'>ARM體系結(jié)構(gòu)本身并不包含除法運(yùn)算硬件，所以在ARM上實(shí)現(xiàn)除法是十分耗時(shí)的。ARM指令集中沒(méi)有直接提供除法匯編指令，當(dāng)代碼中出現(xiàn)除法運(yùn)算時(shí)，ARM編譯器會(huì)調(diào)用C庫(kù)函數(shù)（有符合除法調(diào)用_rt_sdiv，無(wú)符合除法調(diào)用_rt_udiv），來(lái)實(shí)現(xiàn)除法操作。根據(jù)除數(shù)和被除數(shù)的不同，32bit的除法運(yùn)算一般要占有20－140個(gè)指令周期。除法運(yùn)算占用的指令周期，由下面公式計(jì)算。
　　Time（除數(shù)n / 被除數(shù)d）
　　= C0 + C1 * log2（除數(shù)n / 被除數(shù)d） =
　　= C0 + C1 * （log2（除數(shù)） -log2（被除數(shù)））。
　　為了避免在程序中出現(xiàn)除法操作，編程時(shí)盡量使用其他運(yùn)算來(lái)代替除法操作。如，使用x》（z×y）來(lái)代替（x/y）》z。
　　另外，在無(wú)法避免的除法運(yùn)算中，盡量使用無(wú)符合除法代替有符號(hào)除法。這是因?yàn)樵贏RM庫(kù)函數(shù)中，無(wú)符合除法的運(yùn)算速度要快于有符合除法。
　　下面章節(jié)將詳細(xì)討論如何在代碼中提高除法運(yùn)算的執(zhí)行效率。
　　14.2.1 合并除法和求余運(yùn)算
　　ARM的除法運(yùn)算庫(kù)函數(shù)能同時(shí)返回運(yùn)算的商和余數(shù)。
　　在一些同時(shí)需要商和余數(shù)的情況下，編譯器將調(diào)用一次除法運(yùn)算函數(shù)同時(shí)存儲(chǔ)運(yùn)算的商和余數(shù)。
　　下面是一個(gè)編譯器調(diào)用除法庫(kù)，同時(shí)存儲(chǔ)運(yùn)算的商和余數(shù)的例子。
　　源程序如下。
　　int combined_div_mod （int a， int b）
　　{
　　return （a / b） + （a % b）;
　　}
　　下面是編譯器編譯出的匯編代碼。
　　combined_div_mod
　　STMDB sp！，{lr}
　　MOV a3，a2
　　MOV a2，a1
　　MOV a1，a3
　　BL __rt_sdiv
　　ADD a1，a1，a2
　　LDMIA sp！，{pc}
　　從上面的例子可以看出，調(diào)用一次除法運(yùn)算，同時(shí)返回了商和余數(shù)。
　　14.2.2 使用2的整數(shù)次冪做除數(shù)
　　當(dāng)2的整數(shù)次冪做除數(shù)時(shí)，編譯器會(huì)自動(dòng)將除法運(yùn)算轉(zhuǎn)換成移位運(yùn)算。所以在編寫(xiě)程序算法時(shí)，盡量使用2的整數(shù)次冪做除數(shù)。
　　下面的例子顯示了編譯器對(duì)除法運(yùn)算的自動(dòng)優(yōu)化。
　　源程序如下。
　　typedef unsigned int uint;
　　uint div16u （uint a）
　　{ return a / 16;
　　}
　　int div16s （int a）
　　{ return a / 16;
　　}
　　編譯器的編譯結(jié)果如下。
　　div16u
　　MOV a1，a1，LSR #4
　　MOV pc，lr
　　div16s
　　CMP a1，#0
　　ADDLT a1，a1，#&f
　　MOV a1，a1，ASR #4
　　MOV pc，lr
　　從上面的例子可以看出，無(wú)符號(hào)除法的運(yùn)算速度快于有符號(hào)除法。
　　14.2.3 求余運(yùn)算
　　為了避免在程序中使用除法運(yùn)算，可以將一些典型的求余運(yùn)算進(jìn)行轉(zhuǎn)換。下面的例子提供一種轉(zhuǎn)換方法。
　　uint counter1 （uint count）
　　{ return （++count % 60）;
　　}
　　轉(zhuǎn)換成，
　　uint counter2 （uint count）
　　{ if （++count 》= 60）
　　count = 0;
　　return （count）;
　　}
　　下面是兩個(gè)功能函數(shù)編譯后的匯編代碼。
　　counter1
　　STMDB sp！，{lr}
　　ADD a2，a1，#1
　　MOV a1，#&3c
　　BL __rt_udiv
　　MOV a1，a2
　　LDMIA sp！，{pc}
　　counter2
　　ADD a1，a1，#1
　　CMP a1，#&3c
　　MOVCS a1，#0
　　MOV pc，lr
　　上面的例子清晰的顯示了使用if語(yǔ)句代替除法運(yùn)算后，代碼的執(zhí)行效率有很大提高。
　　14.2.4 除數(shù)是常數(shù)的除法
　　因?yàn)槌ê湍＿\(yùn)算執(zhí)行起來(lái)比較慢，所以應(yīng)該盡可能地避免使用。但是除數(shù)是常數(shù)的除法運(yùn)算和用同一個(gè)除數(shù)的重復(fù)除法，執(zhí)行效率會(huì)比較高。在ARM的除法庫(kù)中，存在除數(shù)為10的除法運(yùn)算庫(kù)，其中包括有符號(hào)除法和無(wú)符號(hào)除法。如果除數(shù)是10以外的其他常數(shù)，用戶可以編寫(xiě)自己的功能函數(shù)。ARM的開(kāi)發(fā)工具集中，提供了關(guān)于除數(shù)是常數(shù)的示例程序和算法分析，以供用戶編寫(xiě)自己的代碼時(shí)參考。
?