C語言位運算練習：計算整數二進位中 1 的個數 (Population Count)

基本迴圈法 (逐位檢查)

int count_one_bits(unsigned int n) {
    int count = 0;
    while (n) {
        if (n & 1) count++; // 檢查最低位
        n >>= 1;            // 右移一位
    }
    return count;
}

優化：Brian Kernighan 算法 (只遍歷 1 的位數)

int count_one_bits_fast(unsigned int n) {
    int count = 0;
    while (n) {
        n &= (n - 1); // 清除最低位的 1
        count++;
    }
    return count;
}

原理：n-1 會將最低位 1 變 0，後面 0 變 1。n & (n-1) 正好清除該 1。迴圈次數 = 1 的個數。

查表法 (極致速度)

// 256 bytes 查表
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
};
int count_lookup(unsigned int n) {
    return bits[n & 0xFF] + bits[(n>>8) & 0xFF] + bits[(n>>16) & 0xFF] + bits[n>>24];
}

現代編譯器內建 (最佳實戰)

// GCC/Clang/MSVC (C23 標準化)
int count = __builtin_popcount(n);     // unsigned int
int count_ll = __builtin_popcountll(n); // unsigned long long
// 編譯器會生成單條指令 (x86 POPCNT, ARM CNT)

測試

int main() {
    printf("%d\n", count_one_bits_fast(255)); // 8 (11111111)
    printf("%d\n", __builtin_popcount(0xFFFFFFFF)); // 32
    return 0;
}