二進制中 1 的個數

題目描述：請實現一個函數，輸入一個整數，輸出該數二進制表示中 1 的個數。

例如： 9 表示成二進制是 1001， 有 2 位是 1 。因此如果輸入 9 ，該函數輸出 2 。

先看一種錯誤的解法：

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        if(n & 1)
            count ++;

        n = n >> 1;
    }

    return count;
}

注意：在使用乘法或者除法的運算時，盡量使用移位運算代替，因為移位運算的效率要比乘除法高很多！

上述解法的問題在于：輸入一個正數，結果沒有問題，但是，如果輸入一個負數的話，會發生什么情況？

我們知道，負數的二進制的最高位為 1 ，當進行右移操作時，最高位要補上符號位也就是 1 ，因此每右移一位，最高位就補 1 ，最終這個數字就會變成0xFFFFFFFF，而陷入死循環。

常規解法

int NumberOf1_Solution1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)
            count ++;

        flag = flag << 1;
    }

    return count;
}

此解法中循環的次數等于整數二進制的位數，32位的整數需要循環32次。

高效的解法

int NumberOf1(int n)
{
    int count = 0;

    while (n)
    {
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

該解法在整數中有幾個 1 就只需要循環幾次。

相關題目