LeetCode 191 Number of 1 Bits：漢明重量的多種高效算法

問題描述

給定一個 32 位無符號整數，返回其二進制表示中 '1' 的個數（即漢明重量）。例如 11 (0b1011) 返回 3。

算法演進：從基礎到極致優化

方法一：逐位檢查（基礎版）

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

時間 O(32)，每次只檢查最低位。

方法二：Brian Kernighan 算法（經典優化）

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) {
        n &= (n - 1);  // 消除最低位的 1
        ++count;
    }
    return count;
}

時間 O(1 的個數)，每次循環直接跳過中間的 0。

方法三：查表法（工程實用）

int hammingWeight(uint32_t n) {
    static const unsigned char bits[256] = {
        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4, ... // 預計算 0-255 的 popcount
    };
    return bits[n & 0xFF] + 
           bits[(n >> 8) & 0xFF] + 
           bits[(n >> 16) & 0xFF] + 
           bits[(n >> 24) & 0xFF];
}

O(1) 查表，適合高頻調用場景。

方法四：並行計數 / SWAR (SIMD Within A Register)

int hammingWeight(uint32_t n) {
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);  // 2-bit 計數
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);  // 4-bit 計數
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);  // 8-bit 計數
    n = (n * 0x01010101) >> 24;                      // 加總到最高位
    return n;
}

無分支、指令級並行，現代 CPU 上極快。

方法五：內建函數（編譯器優化）

// GCC/Clang
int hammingWeight(uint32_t n) {
    return __builtin_popcount(n);
}

// MSVC
#include <intrin.h>
int hammingWeight(uint32_t n) {
    return __popcnt(n);
}

直接映射到硬件指令（POPCNT），性能最優。

性能對比參考 (x86-64, -O3)

語言特定注意事項

• Java：無無符號類型，需用 n >>> 1 無符號右移，或調用 Integer.bitCount()
• Python：bin(n).count('1') 或 n.bit_count() (3.10+)
• C++20：std::popcount(n) (<bit>)