Fly me to the moon

9月21日，對(duì)本文從格式到部分內(nèi)容上都進(jìn)行了修改
另外，鑒于某些轉(zhuǎn)載沒(méi)有注明出處，考慮到版權(quán)問(wèn)題，特聲明如下：
作者：翼帆@cppblog 
原文地址：http://www.shnenglu.com/xiaoyisnail/archive/2009/09/19/96707.html
本文版權(quán)歸作者和cppblog共有，歡迎轉(zhuǎn)載，但未經(jīng)作者同意必須保留此段聲明，且在文章頁(yè)面明顯位置給出原文連接，否則保留追究法律責(zé)任的權(quán)利。

    今天看了一位師兄去年的筆經(jīng)總結(jié)，其中有一題是“不許用%和/來(lái)實(shí)現(xiàn)求任意數(shù)除以3的余數(shù)”，我想考官的目的應(yīng)該是想考察學(xué)生對(duì)位運(yùn)算的熟悉程度吧，于是我把題目擴(kuò)展成“只能用+,-和位運(yùn)算實(shí)現(xiàn)正整數(shù)除法(/)和取模(%)”，注意：這里不能使用其它的庫(kù)例程來(lái)輔助計(jì)算，如log,log10等。在思考這道題目的過(guò)程中，我又涉及到了許多二進(jìn)制相關(guān)的題目，如：
    判斷給定的整數(shù)是不是2的整數(shù)次冪
    判斷給定的整數(shù)是不是4的整數(shù)次冪
    求給定整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
    求給定整數(shù)的二進(jìn)制表示中0的個(gè)數(shù)
    求給定整數(shù)的二進(jìn)制表示中最高位1的位置
    求大于等于給定整數(shù)的最小的2的整數(shù)次冪
    求給定整數(shù)的二進(jìn)制表示的有效位數(shù)
    ...
    9月21日補(bǔ)充：這里只考慮值為正整數(shù)的情況。
    這些題目都是經(jīng)典老題，頻繁出現(xiàn)于各類筆試面試題中，除了能考察位運(yùn)算外，還能考察應(yīng)聘者能否給出創(chuàng)新的算法來(lái)更好地解決問(wèn)題。可以說(shuō)這些題目都不難，如果使用32位的int來(lái)表示整數(shù)的話，蠻力法都可以比較好地完成任務(wù)，但是如果想盡可能地提高效率，那就需要?jiǎng)右环X經(jīng)了。下面給出我對(duì)這些問(wèn)題的整理和C++實(shí)現(xiàn)，并在下次的文章中給出只用+,-和位運(yùn)算實(shí)現(xiàn)的正整數(shù)除法和取模。
    從某種意義上講，特別是從充分利用底層硬件的計(jì)算能力(利用特殊的cpu指令)來(lái)看，這些解法肯定不是最優(yōu)的，所以還希望大俠們多多指點(diǎn)。
   
    判斷給定的整數(shù)是不是2的整數(shù)次冪
    這應(yīng)該是最簡(jiǎn)單的，利用最高位是1，其后所有位為0的特性，常數(shù)時(shí)間解決問(wèn)題：

    求給定整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
    考慮到n-1會(huì)把n的二進(jìn)制表示中最低位的1置0并把其后的所有0置1，同時(shí)不改變此位置前的所有位，那么n&(n-1)即可消除這個(gè)最低位的1。這樣便有了比順序枚舉所有位更快的算法：循環(huán)消除最低位的1，循環(huán)次數(shù)即所求1的個(gè)數(shù)。此算法的時(shí)間復(fù)雜度為O(n的二進(jìn)制表示中的1的個(gè)數(shù))，最壞情況下的復(fù)雜度O(n的二進(jìn)制表示的總位數(shù))。
    既然有了求給定整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)的辦法，那么想要求給定整數(shù)的二進(jìn)制表示中0的個(gè)數(shù)就很簡(jiǎn)單了。事實(shí)上，在二進(jìn)制中，完全可以把0和1看作是對(duì)稱的兩個(gè)對(duì)象，取反操作(~)可以任意的切換這兩個(gè)對(duì)象，只要先對(duì)n進(jìn)行一次取反，然后再用上述算法即能得到二進(jìn)制表示中0的個(gè)數(shù)。首先看下面的代碼：
    不知大家有沒(méi)有看出問(wèn)題來(lái)？是的,~操作符會(huì)把所有高位的都取反，而不是只把有效位取反，所以我們需要一個(gè)能保持高位不變的位取反操作，下面是我的實(shí)現(xiàn)，時(shí)間復(fù)雜度和求二進(jìn)制表示中1的個(gè)數(shù)的算法相同，都與二進(jìn)制表示中1的個(gè)數(shù)有關(guān)：
    有了這個(gè)特殊的取反操作，求給定整數(shù)的二進(jìn)制表示中0的個(gè)數(shù)的辦法就簡(jiǎn)單了：
    看到這里，聰明的讀者肯定看出問(wèn)題來(lái)了，其實(shí)我干了一件很蠢的事情。看看上述算法的時(shí)間復(fù)雜度，negate_bits花了O(n的二進(jìn)制表示中1的個(gè)數(shù))，while循環(huán)計(jì)算取反后的n的二進(jìn)制表示中1的個(gè)數(shù)，事實(shí)上就是O(n的二進(jìn)制表示中0的個(gè)數(shù))，兩部分加起來(lái)其實(shí)就是二進(jìn)制表示總的有效位數(shù)，換句話說(shuō)，這個(gè)算法是線性的，而事實(shí)上，我們完全可以先線性地求出這個(gè)總的有效位數(shù)，然后減去1的位數(shù)，即得到0的位數(shù)，根本不用費(fèi)那么大勁去整個(gè)保持高位的取反操作，兩者的時(shí)間復(fù)雜度在漸進(jìn)意義上也是相同的。所以，我犯傻了，但是這里又引出另一個(gè)問(wèn)題：

    求給定整數(shù)的二進(jìn)制表示的有效位數(shù)
    上面提到了線性地求這個(gè)位數(shù)(下文記為m)，即“循環(huán)右移1位，記錄右移次數(shù)”，時(shí)間復(fù)雜度O(m)。但是我想，一看到這個(gè)題目，所有人的第一反應(yīng)應(yīng)該是floor(log₂(n))+1吧，但是請(qǐng)注意，本文在一開(kāi)始就規(guī)定了“不能使用庫(kù)例程”，那么在這個(gè)限制下該怎么做呢？有沒(méi)有比線性時(shí)間更好的算法呢？其實(shí)到目前為止我也沒(méi)有什么特別好的算法，希望誰(shuí)有什么精妙的算法能指點(diǎn)一下，不要打我。。。

 1//求給定整數(shù)的二進(jìn)制表示的位數(shù)，線性算法
 2int count_bit(unsigned int n)
 3{
 4    int r = 0;
 5    while(n)
 6    {
 7        n>>=1;
 8        r++;
 9    }
10    return r;
11}

    求大于等于給定整數(shù)的最小的2的整數(shù)次冪
    首先是最簡(jiǎn)單的思路：求出n的二進(jìn)制表示的總位數(shù)m，于是1<<m即為所求值，當(dāng)然這里要排除n自身就是2的整數(shù)次冪的情況，復(fù)雜度O(m)，實(shí)現(xiàn)如下：
    事實(shí)上這就涉及到上面求二進(jìn)制表示位數(shù)的問(wèn)題，所以目前為止在此基礎(chǔ)上的算法都是線性時(shí)間的。   
    那有沒(méi)有不用計(jì)算位數(shù)m，從而效率更好的算法呢，能不能像在計(jì)算二進(jìn)制表示中1的個(gè)數(shù)時(shí)那樣根據(jù)1的個(gè)數(shù)來(lái)設(shè)計(jì)算法呢？回到那一題中，“n-1會(huì)把n的二進(jìn)制表示中最低位的1置0并把其后的所有0置1”，那么n|=n-1就把n的二進(jìn)制表示中最低位1后的所有0置1，再加上1，那么就把最低位1左移了一位。于是，便有了更好的算法：循環(huán)左移最低位的1，直到n是2的整數(shù)次冪。該算法跟二進(jìn)制表示中的1的個(gè)數(shù)和位置有關(guān)，最壞時(shí)間復(fù)雜度還是O(二進(jìn)制表示位數(shù))，但是比起上一個(gè)實(shí)現(xiàn)，這個(gè)算法在多數(shù)情況下都比上一個(gè)算法快。實(shí)現(xiàn)如下：
    
    最后來(lái)一個(gè)簡(jiǎn)單的擴(kuò)充題目：
    判斷給定的整數(shù)是不是4的整數(shù)次冪
    觀察4的整數(shù)次冪的特征，容易發(fā)現(xiàn)除了滿足n&(n-1)==0外，唯一的1位后的0的個(gè)數(shù)是偶數(shù)，這從4^x=2^2k也能簡(jiǎn)單地得到。這就很直觀地衍生出一個(gè)簡(jiǎn)單的算法：
    算法很直觀，但是比起is_2exp的常數(shù)時(shí)間is_4exp的線性時(shí)間總讓我覺(jué)得不能接受，不過(guò)無(wú)奈還是沒(méi)有想出好辦法來(lái)，哎。。。求大牛指點(diǎn)啊
   
    說(shuō)明：寫這篇文章，已經(jīng)三次丟失全文了，把我快搞瘋了，firefox下好像有點(diǎn)問(wèn)題，先把文章發(fā)上來(lái)，過(guò)會(huì)兒換到IE下繼續(xù)。。。
    再說(shuō)明：換了IE后就沒(méi)再出問(wèn)題了，不過(guò)寫著寫著發(fā)現(xiàn)寫了好久，先歇會(huì)兒，得看書補(bǔ)習(xí)功課了
    最后的說(shuō)明：下次會(huì)給出本文最初提出的問(wèn)題(只能用+,-和位運(yùn)算實(shí)現(xiàn)正整數(shù)除法(/)和取模(%))的實(shí)現(xiàn)。