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