Counting Bits位元計數

01為什麼需要它

看到這些關鍵字就想到它：數 1 的個數、popcount、set bits、漢明距離、有幾個位元不同、n & (n − 1)、清掉最低位的 1、2 的冪次、0 到 n 每個數的位元數。

02核心概念

「一個整數裡有幾個位元是 1」叫做 population count（popcount，也叫 Hamming weight）。最直接的做法是逐位檢查：看最低位 n & 1 加進計數，再 n >>= 1，直到 n 變 0。迴圈次數等於位元長度，和裡面有幾個 1 無關。Brian Kernighan 的做法只在有 1 的地方停：每次執行 n &= n - 1 恰好清掉最低位的那個 1，清幾次 n 才變 0，就有幾個 1。

為什麼 n & (n - 1) 只清掉最低位的 1：設 n 最低位的 1 在第 j 位，那麼第 0 到 j − 1 位全是 0。減 1 需要借位，第 j 位變 0、第 0 到 j − 1 位全變 1，第 j 位以上完全不變。再和原本的 n 做 AND：第 j 位是 1 & 0 = 0，更低的位是 0 & 1 = 0，更高的位是 x & x = x，結果正好是「n 拿掉最低位的 1」。迴圈維持的不變量是 count + popcount(n) 恆等於原數的 1 的個數：每輪 count 加 1、n 少一個 1，n 變 0 時 count 就是答案。同一個式子還能判斷 2 的冪次：n > 0 且 n & (n - 1) == 0，代表 n 只有一個 1。

設 1 的個數是 k、位元寬度是 w。Kernighan 是 O(k)，逐位檢查是 O(位元長度)，最壞都是 O(w)（32 個位元全是 1 時兩者一樣），但 1 越稀疏 Kernighan 越省；兩者都只用 O(1) 空間。要算 0 到 n 每個數的 1 個數（LeetCode 338），每個數各跑一次 Kernighan 總共 O(n log n)；改用遞推 bits[i] = bits[i & (i - 1)] + 1：i & (i - 1) 比 i 小、恰好少一個 1，而且早就填好了，所以整張表 O(n)，除了答案陣列本身不需要額外空間（bits[i >> 1] + (i & 1) 也是一樣的效果）。漢明距離是 popcount(a ^ b)；要算整個陣列所有數對的漢明距離總和，不必 O(n²) 兩兩比，改成逐位看：某一位上有 c 個 1、n − c 個 0，這一位就貢獻 c × (n − c)，總共 O(32n)。

最常見的坑是負數。Python 的整數沒有固定寬度，−1 可以想成有無限多個 1，n &= n - 1 只會得到 −2、−4、−8⋯⋯永遠到不了 0，逐位檢查的 n >>= 1 也會卡在 −1；要先 n &= 0xFFFFFFFF 轉成 32 位元。C++ 要用 std::uint32_t，有號負數右移通常補 1，一樣停不下來。實務上直接用內建：Python 3.10 起的 int.bit_count()、C++ 的 std::bitset<32>(n).count()、GCC/Clang 的 __builtin_popcount、C++20 的 std::popcount，通常會編譯成 CPU 的 POPCNT 指令。自己會寫 Kernighan 的價值在「清掉最低位的 1」這個動作：Subset Enumeration 的 (sub - 1) & mask 是同一種借位，XOR Tricks 用來分組的 diff & -diff、Fenwick Tree 的 i & -i 是它的姊妹式（取出最低位的 1 而不是清掉），Bitmask DP 裡 popcount(mask) 就是子集大小。

03演算法步驟

1. 1先確定寬度與正負號：輸入可能是負數時，Python 先 n &= 0xFFFFFFFF，C++ 改用 std::uint32_t，否則迴圈不會結束。
2. 2count = 0；while n != 0：n &= n - 1（清掉最低位的 1），count += 1。迴圈結束時 count 就是 1 的個數。
3. 3要知道兩個數有幾個位元不同（漢明距離），先算 x = a ^ b，再對 x 做第 2 步。
4. 4要 0 到 n 每個數的答案：開 bits = [0] * (n + 1)，i 從 1 填到 n，bits[i] = bits[i & (i - 1)] + 1，每格 O(1)。
5. 5要所有數對的漢明距離總和：對每個位元位置數出有 c 個數在這一位是 1，累加 c × (n − c)，不要兩兩配對。
6. 6正式程式直接呼叫內建（bit_count()、__builtin_popcount、std::bitset::count）；判斷 2 的冪次寫 n > 0 and n & (n - 1) == 0，C++ 記得加括號。

04互動示範

n = 181 = 10110101₂，8 個位元裡有 5 個 1。前半段是 Brian Kernighan：每一步把 n、n − 1、n & (n − 1) 三列疊在一起，黃色標出這一輪要清掉的最低位 1 所在的位置，n − 1 那一列的綠色是它下面因借位而變成 1 的位（181 是奇數，第一步還看不到綠色）。後半段是逐位檢查：「原本的 n」那一列裡，正在檢查的位是 1 就標綠、是 0 就標黃，檢查過的位變灰。下方的計數區隨時顯示 count 和目前的迴圈次數，最後比較兩者的總次數：Kernighan 5 次，逐位檢查 8 次。

05程式碼

逐位檢查和 Kernighan 兩個版本放在一起對照，接著是兩個延伸：用 bits[i & (i - 1)] + 1 在 O(n) 內填出 0 到 n 的整張表（LeetCode 338），以及逐位計數求所有數對的漢明距離總和（LeetCode 477）。main 裡的例子包含子網路遮罩、負數與 2 的冪次，最後附上內建函式的寫法。

def popcount_naive(n):
    """逐位檢查：看最低位再右移，迴圈次數 = 位元長度"""
    n &= 0xFFFFFFFF                     # 當成 32 位元無號數，負數才不會無限迴圈
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count


def popcount(n):
    """Brian Kernighan：每次清掉最低位的 1，迴圈次數 = 1 的個數"""
    n &= 0xFFFFFFFF
    count = 0
    while n:
        n &= n - 1                      # 清掉最低位的 1，更高的位不動
        count += 1
    return count


def count_bits(n):
    """0..n 每個數的 1 個數（LeetCode 338）。O(n)"""
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i & (i - 1)] + 1  # i & (i-1) 比 i 小、恰好少一個 1，早就算好了
        # 另一種遞推：bits[i] = bits[i >> 1] + (i & 1)
    return bits


def total_hamming_distance(nums):
    """所有數對的漢明距離總和（LeetCode 477）。逐位計數，O(32n)"""
    n, total = len(nums), 0
    for b in range(32):
        ones = sum((x >> b) & 1 for x in nums)
        total += ones * (n - ones)      # 這一位上，每個 1 和每個 0 配成一對
    return total


if __name__ == "__main__":
    print(popcount(181))                # 5（10110101）
    print(popcount_naive(181))          # 5，但迴圈跑了 8 次
    print(popcount(0xFFFFFFC0))         # 26：遮罩 255.255.255.192 就是 /26
    print(popcount(-1))                 # 32（-1 的 32 位元二補數全是 1）
    print(popcount(1 ^ 4))              # 2：1 和 4 的漢明距離
    print(64 & 63 == 0)                 # True：只有一個 1，是 2 的冪次（Python 的 & 比 == 優先）
    print(count_bits(8))                # [0, 1, 1, 2, 1, 2, 2, 3, 1]
    print(total_hamming_distance([4, 14, 2]))  # 6
    print((181).bit_count())            # 5（內建，Python 3.10+；舊版可用 bin(181).count("1")）

06練習題

• LeetCode 191Number of 1 Bits（Kernighan 的原型題）Easy
• LeetCode 461Hamming Distance（先 XOR 再數 1）Easy
• LeetCode 231Power of Two（n & (n − 1) == 0）Easy
• LeetCode 338Counting Bits（O(n) 遞推）Easy
• LeetCode 477Total Hamming Distance（逐位計數）Medium
• LeetCode 2429Minimize XOR（1 的個數固定後，貪心決定放哪幾位）Medium