C 語言計算整數二進制中 1 的個數：多種演算法實作與優化

C 語言計算整數二進制中 1 的個數：多種演算法實作與優化

方法一：基本除二法（易懂，效能一般）

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

方法二：Brian Kernighan 演算法（高效，迴圈次數等於 1 的個數）

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

原理：value - 1 會將最低位的 1 變為 0，後面的 0 變為 1；value & (value-1) 即清除最低位 1。

方法三：查表法（適用於大量重複查詢）

int count_one_bits_lookup(unsigned int value) {
    static const unsigned char bits[256] = {
        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4, /* ... 完整 256 項 */ 
    };
    return bits[value & 0xFF] + bits[(value>>8) & 0xFF] + 
           bits[(value>>16) & 0xFF] + bits[(value>>24) & 0xFF];
}

方法四：編譯器內建函數（最佳效能，GCC/Clang/MSVC 支援）

// GCC/Clang
int count_one_bits_builtin(unsigned int value) {
    return __builtin_popcount(value);
}
// MSVC (需 #include <intrin.h>)
int count_one_bits_msvc(unsigned int value) {
    return __popcnt(value);
}

主程式測試

int main() {
    unsigned int num;
    printf("輸入一個無號整數: ");
    scanf("%u", &num);
    printf("基本法: %d\n", count_one_bits_basic(num));
    printf("BK演算法: %d\n", count_one_bits_bk(num));
    printf("內建函數: %d\n", __builtin_popcount(num));
    return 0;
}

建議

• 一般應用：直接使用編譯器內建函數，效能最好且程式碼最簡潔。
• 面試/教學：掌握 Brian Kernighan 演算法原理，展現位元運算功力。
• 嵌入式無標準庫環境：BK 演算法是最佳折衷。