C語言統計 32 位整數二進制中 1 的個數：位運算實作教學

問題描述

輸入一個 32 位無號整數（十六進制），統計其二進制表示中「1」的個數。這是經典的位運算面試題，也是 popcount (population count) 的基礎實作。

核心程式碼

#include <stdio.h>

int countOnes(int data) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        // 將第 i 位移至最低位，再與 1 進行 AND 運算
        if (((data >> i) & 1) == 1)
            count++;
    }
    return count;
}

int main(void) {
    int val = 0;
    printf("請輸入要統計的 32 位數值 (十六進制) val = 0x");
    scanf("%x", &val);  // %x 讀取十六進制輸入

    printf("0x%x 的二進制中 1 的個數為 %d\n", val, countOnes(val));
    return 0;
}

執行範例

請輸入要統計的 32 位數值 (十六進制) val = 0x5ce6
0x5ce6 的二進制中 1 的個數為 9

驗證： 0x5CE6 = 0101 1100 1110 0110，共 9 個 1。

關鍵知識點解析

1. 區域變數必須初始化

int count = 0; 未初始化的區域變數值不確定，會導致邏輯錯誤。

2. scanf 格式字串差異

• %x：按十六進制讀取，存入變數（如輸入 5ce6 → 值為 0x5CE6）。
• %d：按十進制讀取（如輸入 123 → 值為 123）。

3. 位運算核心邏輯

(data >> i) & 1

• data >> i：將目標位右移至最低位（LSB）。
• & 1：只保留最低位，結果為 0 或 1。

進階優化方向

上述演算法時間複雜度 O(32) = O(1)，但可進一步優化：

• 查表法：預計算 0~255 的 popcount，每次查 4 次表（8 位 × 4 = 32 位）。
• Brian Kernighan 演算法：n &= (n - 1) 每次消除最低位的 1，迴圈次數等於 1 的個數。
• 硬體指令：現代 CPU 提供 POPCNT 指令（GCC/Clang 內建 __builtin_popcount）。

Brian Kernighan 版本範例

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

此版本在 1 的個數較少時極快，最壞情況仍為 32 次迴圈。