這道看似非常簡單的題其實有很多奇妙的解法，看到網上一些神牛的解法實在是嘆為觀止！
不過我們還是按部就班的來：
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 }
沒有多少可以講的，非常簡單，不過這樣做會發現，該算法時間復雜度是O(logN)的
2、為了優化上面算法，盡量做到降低時間復雜度，但是O(logN)的復雜度再降低會是什么樣子呢？O(1)？那就直接建索引？但是畢竟32位整數想要建索引的話那內存耗費就太大了，所以我們先看看能不能使得復雜度將到O(m)，其中m是x中1的個數，那么怎么樣才能每進行一次循環x的1的個數就減1呢？比較難想到的地方就是它了：x & (x - 1)，比如x為12，即1100b，如果進行一次x = x & (x - 1)運算則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中的代碼相似，但是每次循環使問題減小的規模是不一樣的。
3、
該方法是從網上借鑒的，確實不太容易想到，非常的巧妙，采用典型的分治思想：比如我們有一個數字11111111b，基礎情況是先計算每一位的1的個數（這個步驟可以省略，類似歸并排序的基礎情況，對一個元素的排序是不需要排）；再歸并，計算相鄰兩位的1的個數，即第0位和第1位的1的個數為2個，第2位和第3位的1的個數為2個，...，第6位和第7位的1的個數為2個；這樣得到10 10 10 10b，然后再歸并，計算第0,1,2,3位的1的個數，計算第4,5,6,7位的1的個數，得到0100 0100b；然后再歸并得到第0,1,2,3,4,5,6,7位的1的個數為1000b。上面分析的是8位二進制情況，對于32位二進制，同理，只需要繼續歸并即可，代碼如下：
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 }
對于方法3，時間復雜度可以認為是O(1)的，不過真實速度和方法2的pk我確實沒有比較過，因為我們要求的數的位數總不會太大，所以時間差距不會太多，甚至在這種小規模位數的情況下會出現相反結果，不過方法3的思想實在是巧妙，如果沒有對分治算法的透徹理解，是很難想到用分治去解決該題的
領教了！
posted on 2012-09-04 10:52
myjfm 閱讀(628)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎