在程序中，同一個(gè)除數(shù)的除法經(jīng)常會(huì)出現(xiàn)很多次。在前面的例子中，bytes_per_line的值在整個(gè)程序中都是固定不變的。又如3到2笛卡爾坐標(biāo)變換，其中就使用了同一個(gè)除數(shù)兩次：

　　(x，Y，x)→(x/z，y/z)

　　這種情況下，使用cache指令中的值1/z，并使用1/z的乘法來(lái)代替除法運(yùn)算，效率會(huì)更高。另外，要盡可能使用int類型的運(yùn)算，避免使用浮點(diǎn)運(yùn)算。

　　下面將更加偏重于從數(shù)學(xué)和理論的角度分析，把重復(fù)除法轉(zhuǎn)換成乘法運(yùn)算。

　　下面來(lái)區(qū)分精確數(shù)學(xué)意義上的除法和整型除法運(yùn)算：

　　n/d，即整數(shù)n被分成整數(shù)d份，結(jié)果趨向于O(與C語(yǔ)言相同);

　　n%d，即n被d除之后的余數(shù)，就是n--d(n/d);

　　n/d=n·d-1，即真正數(shù)學(xué)意義上的n被d除。

　　當(dāng)使用整型除法時(shí)，最容易估算d-1值的方法是計(jì)算232/d。然后，就可以估算n/d為：

　　(n(232/d))/232 (1)

　　在執(zhí)行n的乘法時(shí)，需要精確到64位。對(duì)于這種方法，會(huì)出現(xiàn)如下問題：

　　為了計(jì)算232/d，由于一個(gè)unsigned int類型的數(shù)據(jù)放不下232，編譯器要使用64位long long類型的數(shù)，而且必須指定除法為(1 ull<<32)/d。這種64位的除法比32位的除法執(zhí)行起來(lái)要慢得多。

　　如果d碰巧是1，那么232/d就不再適合于un—signed int數(shù)據(jù)類型。

　　上面的做法似乎很好，而且解決了這兩個(gè)問題。那么，再來(lái)看一下用(232一1)/d代替232/d。 令

　　s=0xffffffff ul/d (2)

?

　　以上n/d-2，q，n/d+1為整數(shù)值，所以可得q=n/d或q=(n/d)一1，即初步估計(jì)的結(jié)果q與正確值n/d有可能存在偏差1?？梢园l(fā)現(xiàn)，通過計(jì)算余數(shù)r=n—q·d(O≤r<2d)是比較容易的。下面的代碼糾正了這個(gè)結(jié)果：

　　r=n--q*d;/*初步估計(jì)結(jié)果余數(shù)r的范圍為O≤r<2d*/

　　if(r>=d){/*若需要校正*/

　　r-=d;/*校正r，使O≤r

　　n++;/*相應(yīng)商加1進(jìn)行校正*/

　　} /*得正確結(jié)果q=n/d和r=n%d*/

　　下面給出一個(gè)實(shí)例，用上面的算法完成了N個(gè)元素的數(shù)組被d除。首先，計(jì)算上面所說的s值，然后用乘以5來(lái)代替每個(gè)被d除的除法。64位的乘是很容易實(shí)現(xiàn)的，因?yàn)锳RM中有一條指令UMULL，可以進(jìn)行2個(gè)32位數(shù)相乘，給出一個(gè)64位的結(jié)果。

　　void scale(

　　unsigned int*dest; /*目的數(shù)據(jù)*/

　　unsigned int*src; /*源數(shù)據(jù)*/

　　unsignedInt d; /*分母d*/

　　urlslglaedInt N;) /*數(shù)據(jù)長(zhǎng)度*/

　　{

　　unsigned int s=0xFFFFFFFFu/d;

　　do{

　　unsigned int n，q，r;

　　n=*(src++);

　　q=(urtslgrted int)(((unsined tong long)n*s)>>32);

　　r=n*d;

　　if(r>=d){ /*若需要對(duì)商進(jìn)行校正*/

　　q++;

　　}

　　*(dest++)=q;

　　}while(--N);

　　}

　　這里假定除數(shù)和被除數(shù)都是32位的無(wú)符號(hào)整數(shù)。當(dāng)然，使用32位乘法進(jìn)行16位的無(wú)符號(hào)數(shù)計(jì)算，或者使用1 28位乘法進(jìn)行64位數(shù)計(jì)算，運(yùn)算規(guī)則是一樣的?？梢詾樘囟ǖ臄?shù)據(jù)選擇最窄的運(yùn)算寬度。如果數(shù)據(jù)是16位的，那么就設(shè)置s=(216一1)/d，然后用標(biāo)準(zhǔn)的整型乘法來(lái)求值q。

　　4 結(jié)論

　　如果不能避免除法運(yùn)算，那么應(yīng)盡可能使用除法程序同時(shí)產(chǎn)生商n/d和余數(shù)n%d的好處。對(duì)于重復(fù)對(duì)一除數(shù)d的除法.預(yù)先計(jì)算好s=(2k一1)/d，用乘以s的2k位乘法來(lái)代替除以d的k位無(wú)符號(hào)整數(shù)除法，可大大減少由于直接使用除法操作引入的指令周期數(shù)。