C語言統計二進位中 1 的個數：三種演算法遞進優化 (O(k) → O(popcount))

方法一：逐位檢查 O(log n) = 位寬

int count_ones_v1(unsigned int n) {
    int c = 0;
    while (n) {
        if (n & 1) c++;
        n >>= 1;
    }
    return c;
}

方法二：Brian Kernighan 算法 O(1的個數)

int count_ones_v2(unsigned int n) {
    int c = 0;
    while (n) {
        n &= (n - 1); // 清除最低位 1
        c++;
    }
    return c;
}

原理：n-1 翻轉最低位 1 及其後所有位，& 清除該 1。迴圈次數 = 1 的個數。

方法三：查表法 / 硬體指令 O(1)

// 256 字節查表
static const unsigned char table[256] = {0,1,1,2,1,2,2,3,...};
int count_ones_v3(unsigned int n) {
    return table[n & 0xFF] +
           table[(n>>8) & 0xFF] +
           table[(n>>16) & 0xFF] +
           table[n>>24];
}

// 編譯器內建 (最佳實戰)
int count_ones_builtin(unsigned int n) {
    return __builtin_popcount(n); // GCC/Clang
    // MSVC: __popcnt(n) (需 )
}

效能對比 (10^8 次呼叫)

總結

• 教學/面試：掌握 Kernighan 算法原理。
• 生產環境：直接用 __builtin_popcount / C23 stdc_popcount。