C语言bitcount如何高效统计二进制1的位数？

在C语言中，bitcount（位计数）指的是统计一个整数（或二进制序列）中二进制位为1的个数，以下是几种常见的实现方法,从简单到高效：

方法1：逐位检查（简单直观）

int bitcount(unsigned int x) {
    int count = 0;
    while (x) {
        if (x & 1) {  // 检查最低位是否为1
            count++;
        }
        x >>= 1;     // 右移一位，继续检查下一位
    }
    return count;
}

说明：

• 逐位检查最低位，右移直到所有位处理完毕。
• 时间复杂度：O(n)（n为整数的位数，如32位整数需循环32次）。

方法2：利用 x & (x - 1) 清除最低位的1（高效）

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

原理：

• x & (x - 1) 会清除 x 中最低位的1（1010 & 1001 = 1000）。
• 每次循环清除一个1，直到 x 变为0。
• 时间复杂度：O(k)（k为1的个数，比方法1更快）。

方法3：查表法（预计算8位数的1的个数）

static unsigned char bits[256] = {
    // 预计算0-255的二进制中1的个数
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    // ...（省略其余，实际需完整填充256个值）
};
int bitcount(unsigned int x) {
    return bits[x & 0xFF] +       // 处理低8位
           bits[(x >> 8) & 0xFF] + // 处理次低8位
           bits[(x >> 16) & 0xFF] + // 处理次高8位
           bits[(x >> 24) & 0xFF];  // 处理高8位
}

说明：

• 预先计算所有8位数的1的个数，通过查表快速统计。
• 适用于需要频繁调用的场景，时间复杂度：O(1)。

方法4：使用内置函数（编译器优化）

现代编译器通常提供内置函数直接计算1的个数：

#include <immintrin.h>  // 需支持特定指令集（如x86的POPCNT）
int bitcount(unsigned int x) {
    return __builtin_popcount(x);  // GCC/Clang内置函数
}

说明：

• 编译器可能直接生成高效的机器指令（如 POPCNT）。
• 最优性能,但依赖编译器支持。

推荐选择：

• 如果追求通用性和代码简洁性，使用 方法2（x & (x - 1)）。
• 如果性能是关键且编译器支持，优先使用 方法4（__builtin_popcount）。