191. Number of 1 Bits

題目會給定一個 32 bits unsigned integer N，我們需要將N轉換成二進制並且計算有幾個1。最基本的做法是將N轉換成二進制，並且計算餘數為1時的次數。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n > 0){
            if(n&1)
                count++;
            n = n >> 1; // n = n /2
        }
        return count;
    }
};

此時的時間複雜度為θ(log N)，因為每次都除以2。但其實有更快的做法，使迴圈的執行次數降到θ(k)，k為1在二進制中出現的次數，可以先思考一下再看最後面的做法。

我們只要考慮最低有效位元就好，即轉換為二進制後最右邊的1。可以觀察一下如果n變成n-1剛好會是1's complement，兩者取and運算後最低有效位元後面會恰好等於0。例如10(1010) & 9(1001) = 8 (1000)，可以發現第二個1後面全變成0了，留下了次高的有效位元，因此我們可以利用上述的原理修改做法，此時迴圈的次數就會從 log N 下降到 k 次了。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while(n){
            n &= (n-1); 
            count++;
        }
        return count;
    }
};

如果需要更詳細的原理解釋可以參考漢明權重(Hamming weight)