S.l.e!ep.￠%

像打了激速一樣，以四倍的速度運轉，開心的工作
簡單、開放、平等的公司文化；尊重個性、自由與個人價值；

posts - 1098, comments - 335, trackbacks - 0, articles - 1

位運算之美——用+,-和位運算實現整數除法和取模(一)

Posted on 2009-09-20 11:13 S.l.e!ep.￠% 閱讀(3625) 評論(3) 編輯收藏引用所屬分類: Algorithm

??? 今天看了一位師兄去年的筆經總結，其中有一題是“不許用%和/來實現求任意數除以3的余數”，我想考官的目的應該是想考察學生對位運算的熟悉程度吧，于是我把題目擴展成“只能用+,-和位運算實現整數除法(/)和取模(%)”，注意：這里不能使用其它的庫例程來輔助計算，如log,log10等。在思考這道題目的過程中，我又涉及到了許多二進制相關的題目，如：
??? 判斷給定的整數是不是2的整數次冪
??? 判斷給定的整數是不是4的整數次冪
??? 求給定整數的二進制表示中1的個數
??? 求給定整數的二進制表示中0的個數
??? 求給定整數的二進制表示中最高位1的位置
??? 求大于等于給定整數的最小的2的整數次冪
??? 求給定整數的二進制表示的有效位數
??? ...
??? 這些題目都是經典老題，頻繁出現于各類筆試面試題中，除了能考察位運算外，還能考察應聘者能否給出創新的算法來更好地解決問題。可以說這些題目都不難，如果使用32位的int來表示整數的話，蠻力法都可以比較好地完成任務，但是如果想盡可能地提高效率，那就需要動一番腦經了。下面給出我對這些問題的整理和C++實現，并在此基礎上給出原題(只能用+,-和位運算實現整數除法(/)和取模(%)，下文都稱為原題)的實現。
??? 當然，從某種意義上講，特別是從充分利用底層硬件的計算能力(利用特殊的cpu指令)來看，這些解法肯定不是最優的，希望大俠們多多指點。
??? 還要說明的是，下面各題的順序是按照我在思考原題時的思維過程來安排的，在給出原題的實現時會詳細說明。
??? 判斷給定的整數是不是2的整數次冪
??? 這應該是最簡單的，利用最高位是1，其后所有位為0的特性，常數時間解決問題：

1?//判斷n是否是2的正整數冪
2?inline?bool?is_2exp(unsigned int?n)
3?{
4?????return?!(n&(n-1));
5?}

????求給定整數的二進制表示中1的個數
????考慮到n-1會把n的二進制表示中最低位的1置0并把其后的所有0置1，同時不改變此位置前的所有位，那么n&(n-1)即可消除這個最低位的1。這樣便有了比順序枚舉所有位更快的算法：循環消除最低位的1，循環次數即所求1的個數。此算法的時間復雜度為O(n的二進制表示中的1的個數)，最壞情況下的復雜度O(n的二進制表示的總位數)。

//計算n的二進制表示中1的個數
?2

inline?int?count1(unsigned int?n)
?3

{
?4

????int?r?=?0;
?5

????while(n)
?6

????{
?7

????????n?&=?n-1;
?8

????????r++;
?9

????}
10

????return?r;
11

}

??? 既然有了求給定整數的二進制表示中1的個數的辦法，那么想要求給定整數的二進制表示中0的個數就很簡單了。事實上，在二進制中，完全可以把0和1看作是對稱的兩個對象，取反操作(~)可以任意的切換這兩個對象，只要先對n進行一次取反，然后再用上述算法即能得到二進制表示中0的個數。首先看下面的代碼：

//計算n的二進制表示中0的個數
?2

inline?int?count0_wrong(unsigned int?n)
?3

{
?4

????int?r?=?0;
?5

????n?&=?~n;
?6

????while(n)
?7

????{
?8

????????n?&=?n-1;
?9

????????r++;
10

????}
11

????return?r;
12

}

??? 不知大家有沒有看出問題來？是的~操作符會把所有高位的都取反，而不是只把有效位取反，所以我們需要一個能保持高位不變的位取反操作，下面是我的實現，時間復雜度和求二進制表示中1的個數的算法相同，都與二進制表示中1的個數有關：

//保持高位取反
?2

inline?unsigned int?negate_bits(unsigned int?n)
?3

{
?4

????if(n==0)?return?1;
?5

????unsigned int?r=0,?m=~n;
?6

????while(n)
?7

????{
?8

????????r?|=?(n^(n-1))&m;
?9

????????n?&=?n-1;
10

????}
11

????return?r;
13

}

??? 有了這個特殊的取反操作，求給定整數的二進制表示中0的個數的辦法就簡單了：

//計算n的二進制表示中0的個數
?2

inline?int?count0(?unsigned?int?n)
?3

{
?4

????int?r?=?0;
?5

????n?=?negate_bits(n);
?6

????while(n)
?7

????{
?8

????????n?&=?n-1;
?9

????????r++;
10

????}
11

????return?r;
12

}

??? 看到這里，聰明的讀者肯定看出問題來了，其實我干了一件很蠢的事情。看看上述算法的時間復雜度，negate_bits花了O(n的二進制表示中1的個數)，while循環計算取反后的n的二進制表示中1的個數，事實上就是O(n的二進制表示中0的個數)，兩部分加起來其實就是二進制表示總的有效位數，換句話說，這個算法是線性的，而事實上，我們完全可以先線性地求出這個總的有效位數，然后減去1的位數，即得到0的位數，根本不用費那么大勁去整個保持高位的取反操作，兩者的時間復雜度在漸進意義上也是相同的。所以，我犯傻了，但是這里又引出另一個問題：

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

//求給定整數的二進制表示的位數，線性算法
?2

int?count_bit_1(unsigned int?n)
?3

{
?4

????int?r?=?0;
?5

????while(n)
?6

????{
?7

????????n>>=1;
?8

????????r++;
?9

????}
10

????return?r;
11

}

:???求大于等于給定整數的最小的2的整數次冪
????首先是最簡單的思路：求出n的二進制表示的總位數m，于是1<<m即為所求值，當然這里要排除n自身就是2的整數次冪的情況，復雜度O(m)，實現如下：

//求大于等于n的最小的2的正整數冪，方法1
?2

//時間復雜度O(n的二進制位長度)
?3

unsigned int?high_2exp_1(unsigned int?n)
?4

{
?5

????if(n<=1)?return?1;
?6

????if(is_2exp(n))?return?n;
?7

????unsigned int?r?=?1;
?9

????while(n)
10

????{
11

????????n?>>=?1;
12

????????r?<<=?1;
13

????}
14

????return?r;
16

}

??? 事實上這就涉及到上面求二進制表示位數的問題，所以目前為止在此基礎上的算法都是線性時間的。???
??? 那有沒有不用計算位數m，從而效率更好的算法呢，能不能像在計算二進制表示中1的個數時那樣根據1的個數來設計算法呢？回到那一題中，“n-1會把n的二進制表示中最低位的1置0并把其后的所有0置1”，那么n|=n-1就把n的二進制表示中最低位1后的所有0置1，再加上1，那么就把最低位1左移了一位。于是，便有了更好的算法：循環左移最低位的1，直到n是2的整數次冪。該算法跟二進制表示中的1個數和位置有關，最壞時間復雜度還是O(二進制表示位數)，但是比起上一個實現，這個算法在多數情況下都比上一個算法快。實現如下：

//求大于等于n的最小的2的正整數冪，方法2
?2

//計算時間與n的二進制表示中1的個數和位置有關，比方法1效率高
?3

//最壞情況下的時間復雜度與方法1相同
?4

unsigned int?high_2exp_2(unsigned int?n)
?5

{
?6

????if(n<=1)?return?1;
?7

????while(!is_2exp(n))
?9

????{
10

????????n?|=?n-1;
11

????????n++;
12

????}
13

????return?n;
15

}

????
??? 最后來一個簡單的擴充題目：
??? 判斷給定的整數是不是4的整數次冪
????觀察4的整數次冪的特征，容易發現除了滿足n&(n-1)==0外，唯一的1位后的0的個數是偶數，這從4^x=2^2k也能簡單地得到。這就很直觀地衍生出一個簡單的算法：

//判斷n是否是4的整數次冪
?2

bool?is_4exp(unsigned?int?n)
?3

{
?4

????if(!is_2exp(n))?return?false;
?5

????int?bit_len?=?count_bit_1(n)-1;//線性時間求二進制位數
?7

????if((bit_len&0x1)!=1)
?8

????????return?true;
?9

????else
10

????????return?false;
11

}

????算法很直觀，但是比起is_2exp的常數時間is_4exp的線性時間總讓我覺得不能接受，不過無奈還是沒有想出好辦法來，哎。。。求大牛指點啊

??? 說明：寫這篇文章，已經三次丟失全文了，把我快搞瘋了，firefox下好像有點問題，先把文章發上來，過會兒換到IE下繼續。。。
??? 再說明：換了IE后就沒再出問題了，不過寫著寫著發現寫了好久，先歇會兒，得看書補習功課了

??? 最后的說明：下次會基于上面的內容，給本文最初提出的問題(只能用+,-和位運算實現整數除法(/)和取模(%))的實現

Feedback

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

2010-10-25 10:20 by yu

無意中逛到這里，驚喜之。

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

2010-11-18 16:06 by zl

最后的說明：下次會基于上面的內容，給本文最初提出的問題(只能用+,-和位運算實現整數除法(/)和取模(%))的實現
在那里？

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

2011-09-25 12:03 by skyworm

n &= ~n; // 寫錯啦，這個操作之后，n就永遠等于0了。

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: TEA算法在QQ中的應用 Code01 c++MD5加密類羅馬計數法位運算之美——用+,-和位運算實現整數除法和取模(一) Int2Hex n個數中有且僅有一個數出現了奇數次

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

S.l.e!ep.￠%

位運算之美——用+,-和位運算實現整數除法和取模(一)

位運算之美——用+,-和位運算實現整數除法和取模(一)

Feedback

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

日歷

公告

常用鏈接

留言簿(5)

隨筆分類(1107)

隨筆檔案(1098)

文章檔案(1)

相冊

收藏夾(3)

DataStruct

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

S.l.e!ep.￠%

位運算之美——用+,-和位運算實現整數除法和取模(一)

位運算之美——用+,-和位運算實現整數除法和取模(一)

Feedback

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復 更多評論

日歷

公告

常用鏈接

留言簿(5)

隨筆分類(1107)

隨筆檔案(1098)

文章檔案(1)

相冊

收藏夾(3)

DataStruct

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復更多評論

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復更多評論

# re: 位運算之美——用+,-和位運算實現整數除法和取模(一) 回復更多評論