1. 问题背景与核心需求
LeetCode 191题"位1的个数"（Hamming Weight）是计算机科学中一个经典的基础算法问题。题目要求编写一个函数，输入一个无符号整数，返回其二进制表示中'1'的个数。这个问题看似简单，却涉及到位运算、算法优化等计算机科学的核心概念。
在实际开发中，计算二进制中1的个数（即汉明重量）有广泛的应用场景：
- 密码学中的错误检测与纠正
- 图像处理中的像素分析
- 网络协议中的数据校验
- 嵌入式系统中的寄存器操作
提示：理解汉明重量的概念对深入计算机底层原理很有帮助。这也是为什么像Linux内核这样的系统代码中会频繁出现相关操作。
2. 基础解法：逐位检查法
2.1 算法思路与实现
这是最直观的解法——将数字与1进行按位与运算，检查最低位是否为1，然后右移一位继续检查。
int hammingWeight(uint32_t n) { int count = 0; while (n) { count += n & 1; n >>= 1; } return count; }2.2 时间复杂度分析
- 最坏情况下需要检查32位（对于32位无符号整数）
- 时间复杂度：O(32) → O(1)
- 空间复杂度：O(1)
2.3 注意事项
右移操作符的选择：
- 对于无符号数，使用逻辑右移（>>）
- 对于有符号数，使用算术右移（>>>）
循环终止条件：
- 当n变为0时即可终止，不必检查所有32位
性能瓶颈：
- 即使高位全是0，仍然会执行完整循环
3. 优化解法：Brian Kernighan算法
3.1 算法原理
这个巧妙的方法利用了n & (n-1)会将n的最低有效1位变为0的特性。每次执行这个操作都会消除一个1，直到n变为0。
int hammingWeight(uint32_t n) { int count = 0; while (n) { n &= (n - 1); count++; } return count; }3.2 性能优势
- 循环次数等于1的个数
- 对于稀疏的1分布（如0x80000000），只需1次循环
- 平均情况下比逐位检查快很多
3.3 实际应用场景
Linux内核中就使用了类似的优化：
static inline int hweight32(uint32_t w) { w -= (w >> 1) & 0x55555555; w = (w & 0x33333333) + ((w >> 2) & 0x33333333); w = (w + (w >> 4)) & 0x0f0f0f0f; return (w * 0x01010101) >> 24; }4. 极致优化：查表法
4.1 实现思路
预先计算0-255所有数字的汉明重量，然后将32位数分成4个8位段分别查表。
int hammingWeight(uint32_t n) { uint8_t table[256] = { /* 预计算的汉明重量表 */ }; return table[n & 0xff] + table[(n >> 8) & 0xff] + table[(n >> 16) & 0xff] + table[n >> 24]; }4.2 性能特点
- 时间复杂度：O(1)的固定4次操作
- 空间换时间：需要256字节的查找表
- 适合需要频繁调用的场景
4.3 实际应用
这种解法在以下场景特别有用：
- 高频调用的加密算法
- 实时图像处理
- 嵌入式系统对性能要求苛刻的部分
5. 三种解法的对比测试
5.1 测试环境
- CPU: Intel i7-10750H
- 编译器: GCC 9.3.0 -O3优化
- 测试数据: 随机生成的1000万个32位无符号整数
5.2 性能对比
| 算法类型 | 平均耗时(ms) | 相对性能 |
|---|---|---|
| 逐位检查法 | 42.7 | 1x |
| Brian Kernighan | 15.2 | 2.8x |
| 查表法 | 8.9 | 4.8x |
5.3 选择建议
- 开发初期：使用Brian Kernighan算法，良好的平衡性
- 性能关键路径：考虑查表法
- 内存受限环境：选择Brian Kernighan算法
6. 扩展思考：并行计算汉明重量
现代CPU支持SIMD指令，可以进一步优化：
// 使用SSE4.2指令集的POPCNT指令 int hammingWeight(uint32_t n) { return __builtin_popcount(n); }这种硬件级优化可以比查表法快5-10倍，但需要考虑CPU兼容性问题。
7. 常见问题与调试技巧
7.1 为什么我的结果不对？
常见错误：
- 使用了有符号整数导致算术右移
- 忘记初始化计数器
- 循环条件错误（如使用n > 0而不是n != 0）
7.2 如何验证算法正确性？
测试用例建议：
- 全0：0x00000000 → 0
- 全1：0xFFFFFFFF → 32
- 单个1：0x00000001 → 1
- 稀疏1：0x10101010 → 4
7.3 性能优化技巧
- 使用编译器内置函数（如__builtin_popcount）
- 对于特定场景可以特化算法（如已知1很少）
- 考虑缓存友好性（查表法可能引起缓存抖动）
8. 实际工程中的应用案例
Redis的bitcount命令：
- 使用查表法和SIMD指令混合实现
- 针对不同长度的key采用不同策略
比特币挖矿算法：
- 需要频繁计算哈希值的汉明重量
- 使用专用硬件加速
图像处理：
- 计算二值图像的像素密度
- 使用GPU并行计算
9. 进阶学习路径
相关LeetCode题目：
- 颠倒二进制位
- 2的幂
- 比特位计数
计算机系统知识：
- 补码表示法
- 位运算的数学性质
- 硬件指令集优化
推荐书籍：
- 《Hacker's Delight》Henry S. Warren
- 《深入理解计算机系统》Randal E. Bryant
在实际工程中，我倾向于优先使用Brian Kernighan算法，它提供了良好的可读性和性能平衡。只有在确实需要极致性能时才会考虑查表法或硬件指令。对于嵌入式开发，了解这些位操作技巧尤为重要，因为它们经常用于寄存器操作和硬件接口编程。
