高效计算二进制中1的个数（Hamming Weight）的优化

题目

高效计算二进制中1的个数（Hamming Weight）的优化

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

位运算优化,分治思想,并行计算,常数时间优化

快速回答

计算32位整数二进制表示中1的个数（Hamming Weight）的最优解需满足：

• 时间复杂度: O(1)（固定32位操作）
• 空间复杂度: O(1)
• 核心方法:
  1. 使用分治思想并行计算
  2. 通过位掩码和位移实现分组统计
  3. 利用乘法合并结果
• 最优解代码:
  int popcount(uint32_t n) {
  n = n - ((n >> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
  return ((n + (n >> 4) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

问题背景

计算二进制中1的个数（Hamming Weight）是位运算的经典问题。基础解法如逐位检查（O(n)）或 n &= n-1（O(k)）无法满足高性能场景需求。本题要求为32位整数设计O(1)时间复杂度的最优解。

原理说明

采用分治并行计算思想：

1. 将32位划分为16组2位，每组独立计算1的个数（结果范围0-2）
2. 合并为8组4位，计算每组的1个数（范围0-4）
3. 合并为4组8位，计算每组的1个数（范围0-8）
4. 通过乘法一次性合并4组结果

关键技巧：利用位掩码隔离分组，通过位移对齐数据，用乘法实现并行加法。

代码实现与分步解析

int popcount(uint32_t n) {
  // 步骤1: 计算每2位的1个数 (结果存储在每2位中)
  n = n - ((n >> 1) & 0x55555555);  // 0x55 = 01010101

  // 步骤2: 合并相邻2位组为4位组
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);  // 0x33 = 00110011

  // 步骤3: 合并相邻4位组为8位组，并利用乘法合并结果
  n = (n + (n >> 4)) & 0x0F0F0F0F;  // 0x0F = 00001111

  // 步骤4: 通过乘法将4个8位组结果合并到最高8位
  return (n * 0x01010101) >> 24;  // 0x01 = 00000001
}

分步详解：

1. 步骤1:
   公式 n - ((n>>1) & 0x55555555) 等效于每2位执行 ab - 0a = a+b（a,b为比特值）
2. 步骤2:
   相邻2位组合并：(n & 0x33333333) 取低位组，((n>>2) & 0x33333333) 取高位组，相加得4位组的1个数
3. 步骤3:
   相邻4位组合并：(n + (n>>4)) & 0x0F0F0F0F 确保每8位存储其低4位和高4位的和
4. 步骤4:
   乘法 n * 0x01010101 等效于将4个8位组累加到最高8位（数学原理：A + B + C + D = (A<<24) + (B<<16) + (C<<8) + D 的系数和）

最佳实践

• 编译器内置函数: 实际工程中优先使用 __builtin_popcount()（GCC）或 System.Numerics.BitOperations.PopCount()（C#）
• 硬件加速: x86架构的 POPCNT 指令单周期完成计算
• 变种应用: 算法可扩展至64位（调整掩码为0x5555...等）

常见错误

• 忽略整数符号: 未使用无符号整数导致位移错误
• 掩码错误: 错误使用掩码值（如0x33333333误写为0x3333）
• 乘法误解: 认为步骤4可直接返回 n（实际需右移24位）
• 溢出问题: 步骤3未用 & 0x0F0F0F0F 会导致进位污染相邻组

扩展知识

• SIMD并行: AVX2指令集可同时计算多个整数的Hamming Weight
• 大数据应用: 在布隆过滤器、密码学哈希、DNA序列分析中高频使用
• 数学性质: Hamming Weight满足 popcount(x^y) = popcount(x) + popcount(y) - 2*popcount(x&y)
• 历史演进: 算法由Wegner（1960）提出，经Knuth在《TAOCP》中优化推广