題目網址：https://leetcode.cn/problems/number-of-1-bits/

題意：給一無號整數 n, 返回其二進制表示中 1 的個數。

進階：如果多次呼叫此 function, 要如何優化？

Solution 1：

想法：每次判斷 n 的最右 bit 是否為 1, 若是的話, 則 cnt++, 判斷完最右 bit 後將 n 右移一位, 重複以上步驟直到 n == 0 （沒有 1-bit）為止

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;

        while (n > 0) {
            const int rightmost = n & 1;
            if (rightmost == 1) {
                cnt++;
            }
            n >>= 1;
        }

        return cnt;
    }
};
  • time：$O(1)$ ➔ 因為 n 只有 32 bit, 所以最多右移 32 次, 故為 $O(32)$
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：n & (n-1) 會讓 n 最右邊的 1 變為 0（重要）, 每做一次 cnt++, 直到 n == 0 為止

e.g. n = 100

e.g. n = 101

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0;

        while (n > 0) {
            n &= (n - 1);
            cnt++;
        }

        return cnt;
    }
};
  • time：$O(1)$ ➔ 因為 n 只有 32 bit, 所以最多右移 32 次, 故為 $O(32)$
  • space：$O(1)$ ➔ 只需常數空間