統計二進制中 1 的個數：位運算技巧（Brian Kernighan 算法）

統計二進制中 1 的個數：位運算技巧（Brian Kernighan 算法）

題目來源：基礎位運算練習題
核心標籤：位運算、Brian Kernighan 算法、內建函數

題目大意

輸入 n (≤ 50) 組測試，每組一個整數 m，輸出 m 的二進制表示中 1 的個數。例：9 = 1001₂ → 輸出 2。

方法一：朴素除二取餘（模擬轉二進制）

int countOnes(int x) {
    int cnt = 0;
    while (x != 0) {
        if (x % 2 == 1) cnt++;
        x /= 2;
    }
    return cnt;
}

或用位運算 x & 1、x >>= 1，本質相同，時間 O(log x)。

方法二：Brian Kernighan 算法（神級優化）

int bitcount(int x) {
    int count = 0;
    while (x != 0) {
        x &= (x - 1); // 消除最低位的 1
        count++;
    }
    return count;
}

原理：x - 1 會將 x 最低位的 1 變為 0，後面的 0 變為 1。x & (x-1) 精準清除最低位 1。迴圈次數 = 1 的個數，最壞 O(log x)，平均極快。

方法三：編譯器內建函數（最快、最簡）

// GCC/Clang
int cnt = __builtin_popcount(x);        // 32位
int cnt = __builtin_popcountll(x);      // 64位

// MSVC (Visual Studio)
#include 
int cnt = __popcnt(x);                  // 需連結 lib

編譯器會直接生成 CPU 指令（如 x86 POPCNT），單指令完成，零迴圈開銷。

完整 AC 代碼（標準輸入輸出）

#include 

int bitcount(int x) {
    int count = 0;
    while (x) {
        x &= (x - 1);
        count++;
    }
    return count;
}

int main() {
    int n, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &x);
        printf("%d\n", bitcount(x));
    }
    return 0;
}

常見錯誤與避坑

• 負數處理：C 語言右移負數為實現定義（算術/邏輯移位），建議用 unsigned int 或 Brian Kernighan 算法（對補碼負數同樣有效）
• 變量作用域：迴圈內變量 count、one 需在每輪測試重置，否則累加錯誤
• 輸入讀取：scanf("%d", &x) 直接讀整數，無需字符串轉換

擴展：漢明重量應用場景

• 錯誤檢測碼（CRC、海明碼）計算
• 布隆過濾器哈希函數數量優化
• 國際象棋位棋盤表示法（Bitboard）移動生成
• 編譯器優化：__builtin_popcount 用於向量化判斷

統計二進制 1 的個數（Population Count / Hamming Weight）是位運算皇冠上的明珠，Brian Kernighan 算法與內建函數是工程實踐的雙重保障。