1.問題描述

實現一個函數，輸入一個無符號整數，輸出該數二進制中的1的個數。例如把9表示成二進制是1001，有2位是1，因此如果輸入9，該函數輸出2

 

2.分析與解法

解法1：利用十進制和二進制相互轉化的規則，依次除余操作的結果是否為1  代碼如下：

int Count1(unsigned int v){    int num = 0;        while(v)    {         if(v % 2 == 1)         {              num++;           }         v = v/2;    }        return num;}
 
 
解法2：向右移位操作同樣可以達到相同的目的，唯一不同的是，移位之后如何來判斷是否有1存在。對于這個問題，舉例：10100001，在向右移位的過程中，我們會把最后一位丟棄，因此需要判斷最后一位是否為1，這個需要與00000001進行位“與”操作，看結果是否為1，如果為1，則表示當前最后八位最后一位為1，否則為0，解法代碼實現如下，時間復雜度為O(log2v)。
int Count2(unsigned int v){    unsigned int num = 0;        while(v)    {         num += v & 0x01;         v >>= 1;    }    return num;}
 
 
解法3：利用"與"操作，不斷清除n的二進制表示中最右邊的1，同時累加計數器，直至n為0，這種方法速度比較快，其運算次數與輸入n的大小無關，只與n中1的個數有關。如果n的二進制表示中有M個1，那么這個方法只需要循環k次即可，所以其時間復雜度O(M)，代碼實現如下：
int Count3(unsigned int v){    int num = 0;        while(v)    {         v &= (v-1);         num++;    }    return num;}
 
 
編程之美同時給出了8bit的情況下，解法4：使用分支操作，解法5：查表法 再計算32bit無符號整數時，需要將32bit切為4部分 然后每部分分別運用解法4解法5下面僅給出代碼：
解法4：
int Count4(unsigned int v){    int num = 0;        switch(v)    {        case 0x0:             num = 0;             break;        case 0x1:        case 0x2:        case 0x4:        case 0x8:        case 0x10:        case 0x20:        case 0x40:        case 0x80:             num = 1;             break;        case 0x3:        case 0x6:        case 0xc:        case 0x18:        case 0x30:        case 0x60:        case 0xc0:             num = 2;             break;         //.....    }    return num;}
解法5：
unsigned int table[256] =     {                 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,         4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8        };int CountTable(unsigned int v){    return table[v & 0xff] +           table[(v >> 8) & 0xff] +           table[(v >> 16) & 0xff] +           table[(v >> 24) & 0xff] ;}
 
 
網上還給出了 平行算法，思路：將v寫成二進制形式，然后相鄰位相加，重復這個過程，直到只剩下一位。以217（11011001）為例，有圖有真相，下面的圖足以說明一切了。217的二進制表示中有5個1。
 
代碼如下：
int Count6(unsigned int v) {     v = (v & 0x55555555) + ((v >> 1) & 0x55555555) ;     v = (v & 0x33333333) + ((v >> 2) & 0x33333333) ;     v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f) ;     v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff) ;     v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff) ;     return v ; }