二进制位运算进阶：高效统计数字中1的个数

2026年3月6日 互联网

一、问题背景与数学原理

在计算机科学中，二进制位运算是底层优化的核心技能之一。统计非负整数n的二进制表示中1的个数（又称”汉明重量”或”popcount”）是算法面试与系统开发中的高频问题。该问题不仅考察对二进制表示的理解，更涉及位操作、循环优化等关键技术。

数学基础：
二进制数的每一位代表2的幂次方，例如十进制数13的二进制表示为1101，其中包含3个1。通过位操作可以高效提取每一位的值：

  • 右移操作（n >> 1）等价于除以2并向下取整
  • 按位与操作（n & 1）可提取最低位
  • 掩码操作（如0x55555555）可批量处理多位

二、基础解法：逐位检查法

算法思路：
通过循环检查每一位是否为1，统计总数。具体步骤如下：

  1. 初始化计数器count = 0
  2. 循环条件：n > 0
  3. 每次循环：
    • 检查最低位：if (n & 1) count++
    • 右移一位：n = n >> 1

代码实现：

  1. int countOnes(int n) {
  2.     int count = 0;
  3.     while (n > 0) {
  4.         count += n & 1;
  5.         n >>= 1;
  6.     }
  7.     return count;
  8. }

性能分析：

  • 时间复杂度：O(log n)，循环次数等于二进制位数
  • 空间复杂度：O(1)
  • 缺点：对于大数（如32位整数）需循环32次

三、优化解法：Brian Kernighan算法

算法原理：
通过n & (n-1)操作可快速消除最右边的1。例如：

  • n = 10100（十进制20）
  • n-1 = 10011
  • n & (n-1) = 10000（消除了最右边的1）

算法步骤：

  1. 初始化计数器count = 0
  2. 循环条件：n > 0
  3. 每次循环：
    • n = n & (n-1)（消除最右边的1）
    • count++

代码实现：

  1. int countOnesOptimized(int n) {
  2.     int count = 0;
  3.     while (n > 0) {
  4.         n &= n - 1;
  5.         count++;
  6.     }
  7.     return count;
  8. }

性能分析：

  • 时间复杂度：O(k)，其中k为1的个数
  • 空间复杂度：O(1)
  • 优势：对于稀疏的1分布（如0x80000000仅1个1）效率极高

四、查表法：空间换时间

算法思路：
预计算所有8位数的1的个数，将32位数拆分为4个8位段，通过查表快速统计。

实现步骤：

  1. 创建256元素的查找表table[256]，存储0~255的1的个数
  2. 将32位数拆分为4个字节：
    • byte1 = (n >> 24) & 0xFF
    • byte2 = (n >> 16) & 0xFF
    • byte3 = (n >> 8) & 0xFF
    • byte4 = n & 0xFF
  3. 查表求和：count = table[byte1] + table[byte2] + table[byte3] + table[byte4]

代码实现：

  1. // 预计算查找表
  2. static const unsigned char table[256] = {
  3.     0, 1, 1, 2, 1, 2, 2, 3, // 省略部分数据...
  4. };
  6. int countOnesTable(int n) {
  7.     return table[(n >> 24) & 0xFF] + 
  8.            table[(n >> 16) & 0xFF] + 
  9.            table[(n >> 8) & 0xFF] + 
  10.            table[n & 0xFF];
  11. }

性能分析：

  • 时间复杂度：O(1)（4次查表操作）
  • 空间复杂度：O(256)（查找表）
  • 适用场景：对性能要求极高且内存充足的场景

五、并行计算：SIMD指令优化

现代CPU支持SIMD（单指令多数据）指令集，可同时处理多个数据。以SSE4.2指令集为例，其POPCNT指令可直接计算1的个数：

代码示例：

  1. #include <nmmintrin.h> // 包含SSE4.2指令集头文件
  3. int countOnesSIMD(int n) {
  4.     return _mm_popcnt_u32(n);
  5. }

性能分析：

  • 时间复杂度：O(1)（单指令完成）
  • 硬件依赖：需CPU支持SSE4.2指令集
  • 优势：在支持硬件加速的场景下性能最优

六、边界条件与测试用例

关键测试点：

  1. 输入为0：应返回0
  2. 输入为1：应返回1
  3. 输入为全1（如0xFFFFFFFF）：应返回32
  4. 输入为2的幂次方（如0x80000000）：应返回1
  5. 输入为随机数：验证统计正确性

测试代码框架：

  1. #include <assert.h>
  3. void testCountOnes() {
  4.     assert(countOnes(0) == 0);
  5.     assert(countOnes(1) == 1);
  6.     assert(countOnes(0xFFFFFFFF) == 32);
  7.     assert(countOnes(0x80000000) == 1);
  8.     assert(countOnes(13) == 3); // 1101
  9. }

七、应用场景与扩展

  1. 算法优化：在位图（Bitmap）数据结构中统计有效元素数量
  2. 硬件加速：密码学中的位操作（如AES算法）
  3. 系统开发：统计CPU缓存命中率等性能指标
  4. 扩展问题：
    • 统计两个数的二进制表示中不同位的数量（汉明距离）
    • 查找二进制表示中第一个1的位置

八、性能对比总结

方法 时间复杂度 空间复杂度 适用场景
逐位检查法 O(log n) O(1) 教学示例、简单场景
Brian Kernighan算法 O(k) O(1) 通用优化、稀疏1分布
查表法 O(1) O(256) 极致性能、内存充足
SIMD指令 O(1) O(1) 硬件支持、高性能需求

九、最佳实践建议

  1. 默认选择：Brian Kernighan算法，兼顾效率与可移植性
  2. 性能敏感场景：使用查表法或SIMD指令（需评估硬件兼容性）
  3. 代码可读性：在性能要求不高的场景优先选择清晰实现

通过掌握多种实现方法及其适用场景，开发者可根据实际需求选择最优方案，在算法竞赛、系统开发或性能优化中游刃有余。

最新文章