這道看似非常簡(jiǎn)單的題其實(shí)有很多奇妙的解法，看到網(wǎng)上一些神牛的解法實(shí)在是嘆為觀止！
不過我們還是按部就班的來：
1、最容易想到的方法
1 int count_one(unsigned int x) {
2 int count = 0;
3 while (x) {
4 if (x & 1 == 1) {
5 count++;
6 }
7 x >>= 1;
8 }
9 return count;
10 }
沒有多少可以講的，非常簡(jiǎn)單，不過這樣做會(huì)發(fā)現(xiàn)，該算法時(shí)間復(fù)雜度是O(logN)的
2、為了優(yōu)化上面算法，盡量做到降低時(shí)間復(fù)雜度，但是O(logN)的復(fù)雜度再降低會(huì)是什么樣子呢？O(1)？那就直接建索引？但是畢竟32位整數(shù)想要建索引的話那內(nèi)存耗費(fèi)就太大了，所以我們先看看能不能使得復(fù)雜度將到O(m)，其中m是x中1的個(gè)數(shù)，那么怎么樣才能每進(jìn)行一次循環(huán)x的1的個(gè)數(shù)就減1呢？比較難想到的地方就是它了：x & (x - 1)，比如x為12，即1100b，如果進(jìn)行一次x = x & (x - 1)運(yùn)算則x的值為1000b。因此代碼如下：
1 int count_one(unsigned int x) {
2 int count = 0;
3 while (x) {
4 count++;
5 x &= x - 1;
6 }
7 return count;
8 }
上面的代碼看似和方法1中的代碼相似，但是每次循環(huán)使問題減小的規(guī)模是不一樣的。
3、
該方法是從網(wǎng)上借鑒的，確實(shí)不太容易想到，非常的巧妙，采用典型的分治思想：比如我們有一個(gè)數(shù)字11111111b，基礎(chǔ)情況是先計(jì)算每一位的1的個(gè)數(shù)（這個(gè)步驟可以省略，類似歸并排序的基礎(chǔ)情況，對(duì)一個(gè)元素的排序是不需要排）；再歸并，計(jì)算相鄰兩位的1的個(gè)數(shù)，即第0位和第1位的1的個(gè)數(shù)為2個(gè)，第2位和第3位的1的個(gè)數(shù)為2個(gè)，...，第6位和第7位的1的個(gè)數(shù)為2個(gè)；這樣得到10 10 10 10b，然后再歸并，計(jì)算第0,1,2,3位的1的個(gè)數(shù)，計(jì)算第4,5,6,7位的1的個(gè)數(shù)，得到0100 0100b；然后再歸并得到第0,1,2,3,4,5,6,7位的1的個(gè)數(shù)為1000b。上面分析的是8位二進(jìn)制情況，對(duì)于32位二進(jìn)制，同理，只需要繼續(xù)歸并即可，代碼如下：
1 int count_one(unsigned int x) {
2 x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
3 x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
4 x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
5 x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
6 x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
7 return x;
8 }
對(duì)于方法3，時(shí)間復(fù)雜度可以認(rèn)為是O(1)的，不過真實(shí)速度和方法2的pk我確實(shí)沒有比較過，因?yàn)槲覀円蟮臄?shù)的位數(shù)總不會(huì)太大，所以時(shí)間差距不會(huì)太多，甚至在這種小規(guī)模位數(shù)的情況下會(huì)出現(xiàn)相反結(jié)果，不過方法3的思想實(shí)在是巧妙，如果沒有對(duì)分治算法的透徹理解，是很難想到用分治去解決該題的
領(lǐng)教了！
posted on 2012-09-04 10:52
myjfm 閱讀(631)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)