LeetCode如何輸出某個整數(shù)二進制中1的個數(shù)

題目描述

請實現(xiàn)一個函數(shù)，輸入一個整數(shù)，輸出該數(shù)二進制表示中1的個數(shù)。例如把9轉(zhuǎn)換為二進制是1001，有2位是1。因此如果輸入9，該函數(shù)輸出2.

示例1

輸入：0x7FFFFFFF

輸出：31

示例2

輸入：4055

輸出：10

題目解析

設(shè)置一個 flag ，初始時設(shè)置為 1 ，然后與輸入的數(shù) n 進行與 & 運算，結(jié)果不為零，則表明 n 當(dāng)中與 flag 相同位置的二進制位為 1 ，count 加 1，每次 flag 左移一位，直到數(shù) n 所對應(yīng)的二進制的第一位，執(zhí)行次數(shù)為數(shù) n 轉(zhuǎn)化為二進制之后的位數(shù)。

還有一種方法就是面試官喜歡的方式了，僅執(zhí)行數(shù) n 轉(zhuǎn)化為二進制之后 1 個位數(shù)次。

比如 9 的二進制表示為：

 

我們將 9 減 1 ，對應(yīng)的就是 9 的二進制中最右邊的一個 1 變成了 0，其之后的位置全變?yōu)?1 .

 

然后我們將 8 和 9 進行位與運算，并將結(jié)果保存在 n = n & (n-1)=8 ,然后對 n  繼續(xù)重復(fù)上述步驟，直到 n = 0 為止。

8 減去 1 為 7：

 

然后讓 8 和 7 進行與運算，結(jié)果為 0 ，總共執(zhí)行 2 次，9 的二進制中 1 的個數(shù)為 2.

動畫描述

代碼實現(xiàn)

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

        flag = flag << 1;
    }

    return count;
}

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

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

    return count;
}

時間復(fù)雜度

Solution1 的時間復(fù)雜度為數(shù)n 的二進制位數(shù)。

Solution2 的時間復(fù)雜度為數(shù)n的二進制中 1 的個數(shù)。