C 語言位元運算實戰：右移與 AND 運算子計算二進制 1 的個數

C 語言位元運算實戰：右移與 AND 運算子計算二進制 1 的個數

右移運算子 >>

• 無號數：邏輯右移，高位補 0。等價於除以 2 的冪次。
• 有號數：算術右移 (大多數編譯器)，高位補符號位 (負數補 1，正數補 0)。C 標準規定為實作定義行為。

// 15 = 00001111b
15 >> 1 = 7  (00000111b)
15 >> 2 = 3  (00000011b)

位元與運算子 &

常用於遮罩、檢測特定位。1 & 1 = 1，其餘為 0。

計算 1 的個數：兩種演算法

方法一：右移計數法

int count_bits_shift(unsigned int x) {
    int cnt = 0;
    while (x) {
        if (x & 1) cnt++;
        x >>= 1;
    }
    return cnt;
}

方法二：Brian Kernighan 法 (x &= x-1)

int count_bits_bk(unsigned int x) {
    int cnt = 0;
    while (x) {
        x &= (x - 1); // 清除最低位 1
        cnt++;
    }
    return cnt;
}

BK 法迴圈次數等於 1 的個數，對稀疏 1 極快。

完整測試程式

#include <stdio.h>

int main() {
    unsigned int n;
    printf("輸入整數: ");
    scanf("%u", &n);
    printf("右移法: %d\n", count_bits_shift(n));
    printf("BK 法: %d\n", count_bits_bk(n));
    return 0;
}

建議

• 教學/面試：掌握兩種邏輯與 &/>> 特性。
• 生產環境：直接用 __builtin_popcount (GCC/Clang) 或 std::popcount (C++20)。