二进制位1统计：从基础算法到性能优化

1. 问题背景与需求分析

在嵌入式开发、密码学算法实现以及底层系统优化中，统计一个整数二进制表示中"1"的个数是一个经典问题。这个问题看似简单，却涉及到位操作、算法优化以及硬件特性等多个层面的考量。

以常见的应用场景为例：

• 在嵌入式设备中统计传感器信号的有效脉冲
• 密码学中计算汉明重量（Hamming Weight）
• 内存管理中的位图统计
• 图像处理中的像素值分析

2. 基础实现方案

2.1 移位计数法

最直观的实现方式是使用循环和移位操作：

c复制int count_bits_shift(unsigned int num) {
    int count = 0;
    while (num) {
        count += num & 1;
        num >>= 1;
    }
    return count;
}

注意：这里使用unsigned int避免符号位扩展带来的问题。对于有符号数右移，不同编译器可能有不同的实现（算术移位或逻辑移位）。

2.2 位与消除法

Brian Kernighan提出的优化算法可以跳过0位的处理：

c复制int count_bits_kernighan(unsigned int num) {
    int count = 0;
    while (num) {
        num &= (num - 1);
        count++;
    }
    return count;
}

这个算法的精妙之处在于num & (num - 1)会消除num中最右边的1。例如：

• num = 1010(二进制)
• num-1 = 1001
• num & (num-1) = 1000

3. 进阶优化方案

3.1 查表法

对于需要极致性能的场景，可以使用预计算的查找表：

c复制int count_bits_lookup(unsigned int num) {
    static const unsigned char bits_in_byte[256] = {
        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,