C++ 计算二进制中 1 的个数及数字 1 出现次数

利用位运算统计二进制中 1 的个数

在算法题或底层开发中，计算一个整数的二进制表示中包含多少个 1 是常见问题。相比传统的逐位移位判断，利用位运算技巧可以显著提升效率。

核心算法原理

以下代码展示了基于 n & (n - 1) 的计数方法：

int CountOnes(int n) {
    int count = 0;
    while(n) {
        ++count;
        n = n & (n - 1);
    }
    return count;
}

该算法的核心思想是每次消除 n 最右侧（最低位）的那个 1。当 n 变为 0 时，循环结束，count 即为 1 的总数。

逻辑推导分析

理解这一操作的关键在于分析 n - 1 对二进制位的影响：

• 情况一：最右侧位为 1
  若 n 的最右边是 1，则 n - 1 仅将该位变为 0，高位不变。例如 n = 7 (0111_2)，n - 1 = 6 (0110_2)。执行 n & (n - 1) 后结果为 6，成功去除了最右侧的一个 1。
• 情况二：最右侧位为 0
  若 n 的最右边是 0，则减法需要向前借位。借位会一直传递到第一个遇到的 1，并将该 1 变为 0，而该位右侧的所有 0 均变为 1。例如 n = 8 (1000_2)，n - 1 = 7 (0111_2)。此时 n & (n - 1) 相当于将原始 n 中最右侧的 1 置零，且其右侧原本全为零的位通过与操作也保持为零。

性能优势：
此方法的执行次数等于 n 中 1 的个数。相比于遍历所有 32 位（或 64 位）的传统移位方法，当 1 的数量较少时，其运行时间更短，无需进行无意义的移位和判断。

C++ 统计 1 到 n 之间数字 1 的出现次数

另一类常见问题是：给定一个正整数 n，计算从 1 到 n 的所有整数中，数字字符 '1' 总共出现了多少次。这与前文的二进制不同，此处关注的是十进制表示。

问题定义

输入一个正整数 n，输出区间 [1, n] 中所有数字包含 '1' 的次数总和。

示例说明：
若输入 n = 15，则区间内的数字为 1, 2, ..., 9, 10, 11, 12, 13, 14, 15。
其中： - 1 ~ 9 中，只有 "1" 含有 1 个 '1'。
- 10 含有 1 个 '1'。
- 11 含有 2 个 '1'。
- 12 ~ 15 各含 1 个 '1'。
总计：1 + 1 + 2 + 1 + 1 + 1 + 1 = 8 次。

代码实现思路

对于数据规模较小（如 n ≤ 30000）的情况，可以采用直接的模拟法：遍历每个数字，剥离其每一位来判断是否为 1。

#include <iostream>
using namespace std;

int main(){
    int n;
    int cnt = 0; // 用于累计 1 的总个数
    
    cin >> n;
    
    // 遍历从 1 到 n 的每一个数字
    for(int i = 1; i <= n; i++){
        int j = i; // 使用临时变量 j 处理当前数字 i
        
        // 不断对 j 取模和除法，提取每一位
        while(j){ 
            if(j % 10 == 1){  // 判断当前个位是否为 1
                cnt++;        
            }
            j /= 10;          // 去掉个位，准备处理下一位
        }
    }
    
    cout << cnt << endl;
    return 0;
}

代码解析

1. 外层循环：for 循环控制遍历范围 [1, n]，确保每个数字都被检查。
2. 内层循环：while(j) 负责拆解当前数字 i 的十进制各位。通过 j % 10 获取当前最低位，若等于 1 则计数器加一，随后通过 j /= 10 右移一位，直至数字处理完毕。
3. 复杂度：
   设 D 为 n 的位数，K 为平均每个数字的位数（约 log10(n)）。该算法时间复杂度约为 O(n * log10(n))。虽然对于极大数值有更高效的数位动态规划解法，但对于常规练习题及中小规模输入，该方法直观且易于实现。

以上就是 C++ 计算二进制中 1 的个数及统计数字 1 出现次数的详细内容，更多关于 C++ 位运算与基础算法的资料请关注本站其它相关文章！