C語言統計二進制中1的個數：三種算法演進與位運算藝術

統計整數二進制中 1 的個數：從取模到 Brian Kernighan 算法

經典位運算面試題，展示三種遞進算法：取模法、移位法、Brian Kernighan 算法，揭示位運算優雅藝術。

方法一：取模與除二法

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

直觀但較慢，涉及除法運算。

方法二：移位檢測法

int count_one_bit(int num) {
    int count = 0;
    for (int i = 0; i < 32; i++) {  // 假設 32 位 int
        if (num & 1) count++;
        num >>= 1;
    }
    return count;
}

固定 32 次循環，位運算較快，但負數右移實現相關(算術/邏輯移位)。

方法三：Brian Kernighan 算法 (神級優化)

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

核心洞察：n & (n-1) 恰好清除最低位的 1。

n       = 101100
n-1     = 101011
n&(n-1) = 101000  // 最低位 1 被清零

循環次數 = 1 的個數，最優時間複雜度 O(k)，k 為 1 的個數。

算法對比

擴展應用

• 判斷 2 的冪次：(n & (n-1)) == 0
• 交換兩數無臨時變量
• 位掩碼技術

學習感悟

從不理解到掌握 Kernighan 算法，體現了算法學習的積累過程：多接觸經典算法、理解數學本質、鍛鍊位運算思維。編程不僅是語法，更是邏輯與數學之美的實踐。