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.71xBrian Kernighan15.22.8x查表法8.94.8x5.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 ! 07.2 如何验证算法正确性测试用例建议全00x00000000 → 0全10xFFFFFFFF → 32单个10x00000001 → 1稀疏10x10101010 → 47.3 性能优化技巧使用编译器内置函数如__builtin_popcount对于特定场景可以特化算法如已知1很少考虑缓存友好性查表法可能引起缓存抖动8. 实际工程中的应用案例Redis的bitcount命令使用查表法和SIMD指令混合实现针对不同长度的key采用不同策略比特币挖矿算法需要频繁计算哈希值的汉明重量使用专用硬件加速图像处理计算二值图像的像素密度使用GPU并行计算9. 进阶学习路径相关LeetCode题目颠倒二进制位2的幂比特位计数计算机系统知识补码表示法位运算的数学性质硬件指令集优化推荐书籍《Hackers Delight》Henry S. Warren《深入理解计算机系统》Randal E. Bryant在实际工程中我倾向于优先使用Brian Kernighan算法它提供了良好的可读性和性能平衡。只有在确实需要极致性能时才会考虑查表法或硬件指令。对于嵌入式开发了解这些位操作技巧尤为重要因为它们经常用于寄存器操作和硬件接口编程。 LeetCode 191题解析：汉明重量的三种高效算法
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.71xBrian Kernighan15.22.8x查表法8.94.8x5.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 ! 07.2 如何验证算法正确性测试用例建议全00x00000000 → 0全10xFFFFFFFF → 32单个10x00000001 → 1稀疏10x10101010 → 47.3 性能优化技巧使用编译器内置函数如__builtin_popcount对于特定场景可以特化算法如已知1很少考虑缓存友好性查表法可能引起缓存抖动8. 实际工程中的应用案例Redis的bitcount命令使用查表法和SIMD指令混合实现针对不同长度的key采用不同策略比特币挖矿算法需要频繁计算哈希值的汉明重量使用专用硬件加速图像处理计算二值图像的像素密度使用GPU并行计算9. 进阶学习路径相关LeetCode题目颠倒二进制位2的幂比特位计数计算机系统知识补码表示法位运算的数学性质硬件指令集优化推荐书籍《Hackers Delight》Henry S. Warren《深入理解计算机系统》Randal E. Bryant在实际工程中我倾向于优先使用Brian Kernighan算法它提供了良好的可读性和性能平衡。只有在确实需要极致性能时才会考虑查表法或硬件指令。对于嵌入式开发了解这些位操作技巧尤为重要因为它们经常用于寄存器操作和硬件接口编程。