Thinking Notes

汉明权重-位值中1的个数

7分钟阅读

你提供的这段代码是 popcount64c，是用于计算64位整数汉明权重（1的个数）的分治法经典实现。它常被称为SWAR算法（SIMD within a register），在常数时间内完成计算，且不依赖硬件POPCNT指令。下面我将逐行详细解析，并附上完整的实现。

完整代码及掩码定义

// 常量掩码
const uint64_t m1  = 0x5555555555555555; // 01010101...
const uint64_t m2  = 0x3333333333333333; // 00110011...
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; // 00001111...
const uint64_t h01 = 0x0101010101010101; // 用于求和
 
int popcount64c(uint64_t x)
{
    // 步骤1: 每2位统计其中的1的个数，结果存储在原来的2位中
    x -= (x >> 1) & m1;             // 2位分组计数
    
    // 步骤2: 每4位统计其中的1的个数，结果存储在原来的4位中
    x = (x & m2) + ((x >> 2) & m2); // 4位分组计数
    
    // 步骤3: 每8位统计其中的1的个数，结果存储在原来的8位中
    x = (x + (x >> 4)) & m4;        // 8位分组计数
    
    // 步骤4: 将8个8位的计数相加，结果在最高8位中
    return (x * h01) >> 56;         // 最终求和
}

详细解析

前提与思路

  • 基本思想是分而治之：将64位数划分为多个小组，先统计小组内的1的个数，然后合并结果。
  • 每一步都将分组大小加倍，最终得到总数。

步骤1: 2位分组统计

x -= (x >> 1) & m1;

目的：每2位（bit pair）独立计算其中1的个数，将结果（0, 1, 2）存储在这2位中。

掩码 m1 = 0x5555... = 01010101...

  • 作用：屏蔽奇数位（最低位开始第1、3、5…位）。

运算分析：

  • x >> 1：右移1位，将每对bit的高位移动到低位。
  • (x >> 1) & m1：保留原数偶数位的值（对应每对bit的高位）。
  • x - ...：相当于从原始2位值中减去高位值。

数学上：对于一个2位组 [b1 b0]（b1高位，b0低位）：

  • 原值 = 2*b1 + b0
  • 减去的高位值 = b1
  • 结果 = (2*b1 + b0) - b1 = b1 + b0 ← 正好是1的个数

结果范围：每2位存储0、1或2（二进制00、01或10）。

示例：

初始: x = 0110 1101 ... (按2位分组)
分组: |01|10|11|01|... 
计数:  1  2  2  1  ... (以2位二进制存储)

步骤2: 4位分组统计

x = (x & m2) + ((x >> 2) & m2);

目的：将相邻的2个2位计数相加，得到4位组内的总计数。

掩码 m2 = 0x3333... = 00110011...

  • 作用：每4位中，屏蔽低2位或高2位。

运算分析：

  • x & m2：获取每个4位组的低2位计数。
  • (x >> 2) & m2：获取每个4位组的高2位计数（右移到低位）。
  • 两者相加：将相邻的2位计数合并为4位计数。

结果范围：每4位存储0-4（二进制0000到0100）。

步骤3: 8位分组统计

x = (x + (x >> 4)) & m4;

目的：将相邻的2个4位计数相加，得到8位组内的总计数。

掩码 m4 = 0x0F0F... = 00001111...

  • 作用：每8位中，屏蔽低4位（保留低4位结果）。

运算分析：

  • x + (x >> 4)：将每个8位组的高4位计数加到低4位上。
  • & m4：屏蔽高4位（因为低4位已包含完整计数，高4位可能产生进位干扰）。

结果范围：每8位存储0-8（二进制0000 0000到0000 1000）。

步骤4: 合并所有8位组

return (x * h01) >> 56;

目的：将8个8位组的计数全部相加，得到最终的1的总数。

魔法数 h01 = 0x0101010101010101

  • 每个字节（8位）都是0x01（二进制00000001）。

乘法原理：

  • 将x视为一个由8个字节组成的数：[B7 B6 B5 B4 B3 B2 B1 B0]
  • 乘以h01相当于： 
    x * 0x0101010101010101 = 
  x + (x << 8) + (x << 16) + ... + (x << 56)
  • 结果最高字节（56-63位）包含： 
    B7 + (B6 + B7) + (B5 + B6 + B7) + ... + (B0 + B1 + ... + B7)
但实际效果是：B7 + B6 + B5 + B4 + B3 + B2 + B1 + B0
    因为每个字节最大为8（<16），加法不会跨字节进位。

右移56位：取出最高字节，即为总和。

示例：

x = 0x0302050004010007 (每字节是一个8位组的计数)
乘法后最高字节 = 3+2+5+0+4+1+0+7 = 22

算法特点

优点

  1. 无分支：避免分支预测失败，性能稳定。
  2. 常数时间：无论1的个数多少，固定执行这些操作。
  3. 纯算术运算：仅使用移位、与、加、减、乘，不需要查表。
  4. 并行性：在单个寄存器内隐式并行处理所有分组。

性能

  • 在现代CPU上，通常比朴素的位循环快得多。
  • 但通常不如硬件POPCNT指令（单周期）。
  • 在需要跨平台、保证无特定指令集支持时是最优选择之一。

变体与扩展

  • 32位版本：将掩码改为32位，最后使用(x * 0x01010101) >> 24。
  • 可扩展至更宽的字长，原理相同。

总结

这段代码是分治法计算汉明权重的优雅实现，通过巧妙的掩码和移位操作，在O(1)时间内完成计算。它展示了位级并行计算的经典技巧，是高效位操作算法的典范。

关系图谱