作者：翼帆@cppblog
原文地址：http://www.shnenglu.com/xiaoyisnail/archive/2009/09/21/96883.html
本文版權(quán)歸作者和cppblog共有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責(zé)任的權(quán)利。
終于有時(shí)間寫本文的第二部分了。在上一篇文章(下文中稱為“文(一)”)中，我提出了一個(gè)具體的問題“只能用+,-和位運(yùn)算實(shí)現(xiàn)正整數(shù)除法(/)和取模(%)”，并整理了一些和位運(yùn)算相關(guān)的題目和算法，本文將給出上述問題的一個(gè)完整的解答思路和實(shí)現(xiàn)。
首先思考最簡(jiǎn)單的除法實(shí)現(xiàn)，即循環(huán)減除數(shù)，減到不能再減為止，所減次數(shù)即所求的商，事實(shí)上這就是我們初學(xué)四則運(yùn)算時(shí)對(duì)除法的定義，實(shí)現(xiàn)：
1
int integer_div_0(int dividend, int divisor)
2
{
3
if(divisor == 0)
4
{
5 cout<<"非法參數(shù)，除零錯(cuò)"<<endl;
6 exit(1);
7
}
8
9 int res = 0;
10 while((dividend-=divisor)>=0)
11 ++res;
12
13 return res;
14
}
很顯然，這個(gè)簡(jiǎn)單的實(shí)現(xiàn)是非常低效的，求integer_div_0(a,b)的時(shí)間復(fù)雜度為O(a/b)，當(dāng)a很大b很小時(shí)，計(jì)算開銷很大，有什么辦法能提高效率嗎？考慮到循環(huán)減除數(shù)同時(shí)比較差是否大于等于0有點(diǎn)類似于在一個(gè)一個(gè)數(shù)組或是linked list中順序搜索某個(gè)目標(biāo)值，在較差的情況下近似于搜索整個(gè)問題空間，這樣的開銷必然很大，那么只要找到某個(gè)方法來減少需要搜索的問題空間就可以提高性能了。于是，自然可以想到如下算法：以除數(shù)為初始測(cè)試值，以2的指數(shù)為步長(zhǎng)來搜索問題空間，當(dāng)被除數(shù)與測(cè)試值的差小于除數(shù)時(shí)便結(jié)束搜索，若在這之前測(cè)試值大于被除數(shù)，則將被除數(shù)減去前一個(gè)測(cè)試值，并重復(fù)上述過程直到搜索結(jié)束。舉個(gè)例子，求1200/3：
順序搜索時(shí)，我們要與1200比較的數(shù)有：3,6,9,12,15,...,1998,2001，比較次數(shù)667次
以2的指數(shù)為步長(zhǎng)搜索時(shí)，與1200比較3,6,12,24,48,96,192,384,768,1536，然后與1200-768=432再進(jìn)行比較3,6,12,24,48,96,192,384,768，再取432-384=48比較3,6,12,24,48，搜索結(jié)束，比較次數(shù)共24次，比順序搜索有很大的提高。你可能會(huì)問，為什么要以2的指數(shù)為步長(zhǎng)來搜索呢？答案是，這樣我們就可以使用位操作來進(jìn)一步提高計(jì)算效率了。下面是這個(gè)算法的實(shí)現(xiàn)：
1int integer_div_1(unsigned int dividend, unsigned int divisor)
2{
3 if(divisor == 0)
4 {
5 cout<<"非法參數(shù)，除零錯(cuò)"<<endl;
6 exit(1);
7 }
8
9 if(dividend < divisor) return 0;
10 unsigned int k=0,c=divisor, res=0;
11
12 for(;dividend>=c;c<<=1,k++)
13 if(dividend-c < divisor)
14 return 1<<k;
15
16 return integer_div_1(dividend-(c>>1), divisor)+(1<<(k-1));
17}
注意到最后一行的尾遞歸，再把代碼優(yōu)化為非遞歸如下：
1//非遞歸整數(shù)除法
2int integer_div_2(unsigned int dividend, unsigned int divisor)
3{
4 if(divisor == 0)
5 {
6 cout<<"非法參數(shù)，除零錯(cuò)"<<endl;
7 exit(1);
8 }
9
10 if(dividend < divisor) return 0;
11 unsigned int k, c, res=0;
12
13 while(dividend > divisor)
14 {
15 for(k=0,c=divisor;dividend>=c;c<<=1,k++)
16 {
17 if(dividend-c < divisor)
18 {
19 res += 1<<k;
20 break;
21 }
22 }
23 if(dividend-c < divisor)
24 break;
25
26 res += 1<<(k-1);
27 dividend -= c>>1;
28 }
29
30 return res;
31}
最后，有了整數(shù)除法，取模運(yùn)算就很簡(jiǎn)單了，從進(jìn)行整數(shù)除法搜索商的最后一步立刻就能得到模除的余數(shù)，實(shí)現(xiàn)如下，為了方便起見，代碼里使用C++ STL中的pair模板以同時(shí)返回商和余數(shù)：
1//整數(shù)除法and取模，返回商和余數(shù)
2pair<int,int> integer_div_3(unsigned int dividend, unsigned int divisor)
3{
4 if(divisor == 0)
5 {
6 cout<<"非法參數(shù)，除零錯(cuò)"<<endl;
7 exit(1);
8 }
9
10 if(dividend < divisor)
11 return make_pair(0, dividend);
12 unsigned int k, c, quotient=0, remainder;
13
14 while(dividend > divisor)
15 {
16 for(k=0,c=divisor;dividend>=c;c<<=1,k++)
17 {
18 if(dividend-c < divisor)
19 {
20 quotient += 1<<k;
21 remainder = dividend-c;
22 break;
23 }
24 }
25 if(dividend-c < divisor)
26 break;
27
28 quotient += 1<<(k-1);
29 dividend -= c>>1;
30 }
31
32 return make_pair(quotient, remainder);
33}
寫到這里，算是把全文的任務(wù)都完成了，讀者可能覺得文(一)和文(二)里講到的一些題目的關(guān)系不大，但我寫這兩篇文章的目的就是想強(qiáng)調(diào)位運(yùn)算的作用，或者說二進(jìn)制的美，很多時(shí)候如果我們換個(gè)角度，用二進(jìn)制來思考問題，也許會(huì)突然“Aha!Insight!”，從而得到一個(gè)優(yōu)美的解答。
附上代碼：
http://www.shnenglu.com/Files/xiaoyisnail/bits.rar