C 語言位運算技巧：統計整數二進制中 1 的個數

C 語言位運算技巧：統計整數二進制中 1 的個數

經典 Brian Kernighan 演算法：n &= (n-1) 每次清除最低位 1，迴圈次數等於 1 的個數。

實作程式碼

#include <stdio.h>

int popcount(int n) {
    int count = 0;
    while (n) {
        count++;
        n &= (n - 1);
    }
    return count;
}

int main() {
    printf("10 (1010) -> %d\n", popcount(10));   // 2
    printf("0 -> %d\n", popcount(0));             // 0
    printf("-1 (全1) -> %d\n", popcount(-1));     // 32 (32-bit)
    return 0;
}

演算法對比

標準庫與編譯器支援

• GCC/Clang: __builtin_popcount (unsigned int), __builtin_popcountll (unsigned long long)。
• C++20: std::popcount (<bit>)。
• Java: Integer.bitCount()。
• Python: int.bit_count() (3.10+)。

擴展：統計 0 的個數

int count_zeros(int n) {
    return 32 - popcount(n); // 32-bit
}

應用場景

• 位圖索引、Bloom Filter 位陣列統計。
• 權值計算、熵編碼。
• 檢測 2 的冪：popcount(n) == 1。
• 格雷碼相鄰碼距離恆為 1。