統計整數二進制表示中1的個數

三種比較好的方法：

（1）複雜度為 

int test(int n)
{
    int count=0;
    while(n != 0){
        count += n&1;
        n >>= 1;
    }
    return count;
}
           

（2）

int test(int n)
{
    int count=0;
    while(n != 0){
        n &= n-1;
        count ++;
    }
    return count;
}
           

（3）

int test(int n)
{
    n = (n&0x55555555) + ((n>>1)&0x55555555);
    n = (n&0x33333333) + ((n>>2)&0x33333333);
    n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
    n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
    n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
 
    return n;
}
           

比如這個例子，143的二進制表示是10001111，這裡隻有8位，高位的0怎麼進行與的位運算也是0，是以隻考慮低位的運算，按照這個算法走一次

+---+---+---+---+---+---+---+---+

| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |   <---143

+---+---+---+---+---+---+---+---+

|  0 1  |  0 0  |  1 0  |  1 0  |   <---第一次運算後

+-------+-------+-------+-------+

|    0 0 0 1    |    0 1 0 0    |   <---第二次運算後

+---------------+---------------+

|        0 0 0 0 0 1 0 1        |   <---第三次運算後，得數為5

+-------------------------------+

基本思路：先算出相鄰兩位1的個數，然後在算出相鄰四位的個數，遞推到最後32位。