C語言基礎練習：計算二進制中 1 的個數

C語言基礎練習：計算二進制中 1 的個數

這是一個經典的位運算入門題目：給定一個無號整數，統計其二進制表示中 1 的個數（即人口計數，Population Count）。雖然邏輯簡單，但蘊含了位運算、循環控制與函數設計等核心基礎知識。

基礎實作：逐位檢查法

#include <stdio.h>

int count_one_bit(unsigned int num) {
    int count = 0;
    while (num) {
        if (num % 2 == 1)  // 或 num & 1
            count++;
        num = num / 2;     // 或 num >>= 1
    }
    return count;
}

int main() {
    unsigned int val = 255u;  // 二進制 11111111
    printf("%d\n", count_one_bit(val));  // 輸出 8
    return 0;
}

程式碼解析

• 參數型別用 unsigned int：避免負數右移時的算術位移問題，確保邏輯右移。
• 循環條件 while (num)：當數值變為 0 時結束，比固定 32 次迴圈更高效。
• 取模與除法：num % 2 相當於檢查最低位；num / 2 相當於右移一位。現代編譯器會自動優化為位運算指令。

進階優化：Brian Kernighan 演算法

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

原理：n & (n-1) 能將最低位的 1 翻轉為 0。迴圈執行次數等於 1 的個數，最佳情況 O(1)，最壞 O(log n)，比逐位檢查快得多。

硬體指令加速（GCC/Clang）

int count_one_bit_builtin(unsigned int num) {
    return __builtin_popcount(num);  // 編譯器內建函數，通常對應 POPCNT 指令
}

效能比較（以 10 億次隨機數為例）

常見錯誤與避坑指南

1. 使用有號整數：右移負數時會補 1（算術位移），導致無限迴圈。
2. 忽略 0 的特殊情況：while (num) 自然處理了 0 返回 0。
3. 固定 32 次迴圈：雖然正確但效率低，無法利用提前結束優勢。

學習心得

「這個程式其實是 C 語言中很簡單的一個，但是在和同學討論時我還是感覺自己有一些細節沒有很清楚，這就代表我的 C 語言基礎還是不扎實。所以，我感覺要學好一門語言一定要把基礎打好，不在乎學得多，但是一定要消化好學過的知識。還有要多動手，這樣才能找出問題才會知道需要學的還很多。」

這段話道出了程式設計學習的核心：**基礎決定上限，動手驗證細節，反思沉澱才能內化為能力。**