高效统计二进制数中1的个数大于0的算法优化

1. 问题定义与背景理解

在编程竞赛和算法面试中，二进制数位操作类题目一直是高频考点。今天我们要探讨的是一个典型的二进制统计问题：如何高效统计1~n范围内所有满足"二进制表示中1的个数大于0的个数"的整数数量？这类数我们暂且称为A数（满足条件的数），其余称为B数。

这个问题看似简单，实则考察了多个核心能力：

• 二进制数的位操作技巧
• 数学组合思维
• 算法优化意识
• 边界条件处理能力

在实际应用中，这类统计常用于：

• 密码学中的特定位模式分析
• 硬件设计中的信号编码校验
• 数据压缩算法的特征检测

2. 暴力解法与性能分析

2.1 基础实现思路

最直观的解法是遍历1到n的每个数，统计其二进制表示中1和0的个数：

cpp复制int countA_numbers(int n) {
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        int ones = 0, zeros = 0;
        int num = i;
        while (num > 0) {
            if (num & 1) ones++;
            else zeros++;
            num >>= 1;
        }
        if (ones > zeros) count++;
    }
    return count;
}

2.2 复杂度分析

这种方法的时间复杂度是O(nlogn)，因为：

• 外层循环执行n次
• 内层while循环次数取决于数字的二进制位数（⌊log₂n⌋+1）

当n=1e6时，在我的i7-11800H测试机上耗时约120ms。对于更大的n（如1e9），这种暴力方法显然不适用。

2.3 优化方向思考

暴力法的主要问题在于：

1. 重复计算：相邻数字的二进制表示往往有大量重叠部分
2. 位统计效率：逐位检查的方式没有利用CPU的并行处理能力

3. 基于位运算的优化方案

3.1 内置函数优化

现代CPU提供了专门的指令来计算二进制中1的个数（POPCNT）。在C++中可以通过__builtin_popcount使用：

cp复制