二进制位操作：统计1比0多的数字数量

1. 问题定义与场景解析

在编程竞赛和算法面试中，二进制位操作类题目出现的频率相当高。最近遇到一个有趣的问题：统计1到n范围内所有满足"二进制表示中1的个数大于0的个数"的整数数量。这类数字我们暂且称为A数，不满足的称为B数。

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

• 整数到二进制的转换能力
• 位运算的灵活运用
• 算法效率的优化意识
• 边界条件的处理能力

实际应用场景包括：

• 密码学中的位模式分析
• 硬件设计中的信号处理
• 数据压缩算法的优化
• 机器学习特征工程中的位特征提取

2. 基础解法实现

2.1 逐数字统计法

最直观的解法是对每个数字进行二进制转换并统计比特位：

cpp复制#include <iostream>
using namespace std;

bool isANumber(int x) {
    int ones = 0, zeros = 0;
    while(x > 0) {
        if(x & 1) ones++;
        else zeros++;
        x >>= 1;
    }
    return ones > zeros;
}

int countANumbers(int n) {
    int count = 0;
    for(int i = 1; i <= n; ++i) {
        if(isANumber(i)) count++;
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    cout << countANumbers(n) << endl;
    return 0;
}

注意：这种方法需要处理前导零的问题。比如数字5(101)实际上在32位系统中是000...000101，但通常我们只关心有效位。

2.2 使用内置函数优化

现代编译器提供了计算二进制1个数的内置函数：

cpp复制#include <bitset>
#include <iostream>
using namespace std;

int countANumbers(int n) {
    int count = 0;
    for(int i = 1; i <= n; ++i) {
        int ones = __builtin_popcount(i);
        int bits = 32 - __builtin_clz(i);
        if(ones > bits - ones) count++;
    }
    return count;
}

不同平台的内置函数：

• GCC/Clang: __builtin_popcount
• Windows: __popcnt
• C++20: std::popcount

3. 数学规律与优化算法

3.1 二进制数位DP解法

对于大范围的n（比如1e18），我们需要更高效的算法。数位DP可以解决这类问题：

cpp复制#include <cstring>
#include <iostream>
using namespace std;

int dp[32][32][32]; // pos, ones, zeros

int dfs(int pos, int ones, int zeros, bool tight, const string &s) {
    if(pos == s.length()) return ones > zeros;
    if(!tight && dp[pos][ones][zeros] != -1) 
        return dp[pos][ones][zeros];
    
    int limit = tight ? (s[pos]-'0') : 1;
    int res = 0;
    for(int d = 0; d <= limit; ++d) {
        bool new_tight = tight && (d == limit);
        if(d == 1) res += dfs(pos+1, ones+1, zeros, new_tight, s);