位運算---整數的二進制表達中有多少個1

【題目】

　　給定一個32位整數n，可正、可負、可0.傳回該整數二進制表達中1的個數。

【基本思路】

　　最簡單的方法。整數n每次進行無符号右移一位，檢查最右邊的bit是否為1來進行統計即可。

下面是使用c++實作的代碼：

int count1(int n)
{
    unsigned int num = (unsigned)n;
    int res = ;
    while(num != )
    {
        res += num & ;
        num = num >> ;
    }
    return res;
}
           

上述方法最壞情況下要進行32次循環，接下來介紹兩個循環次數隻與1的個數有關的解法。

int count2(int n)
{
    int res = ;
    while(n != )
    {
        n -= n & (~n + );
        res++;
    }
    return res;
}
           

每次進行n -= n & (~n + 1)操作時就是移除最右邊1的過程。n & (~n + 1)的含義就是得到n中最右邊的1。例如，n = 01000100, n & (~n + 1) = 00000100, n - n & (~n + 1) = 01000000。

int count3(int n)
{
    int res = ;
    while(n != )
    {
        n = n & (n-);
        res++;
    }
    return res;
}
           

n = n & (n-1)這也是移除最右側1的過程。例如： n = 01000100, n-1 = 01000011, n & (n-1) = 01000000。