C++求1到n中1出现的次数以及数的二进制表示中1的个数

C++求1到n中1出现的次数

题目描述

给定一个整数 n，求出从 1 到 n 中数字 1 出现的次数。

示例 1

输入: n = 13
输出: 6
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13。

实现思路

本题需要一些数学知识和代码技巧。我们可以分三个部分来考虑：

1. 设定一个变量 count，用来记录数字 1 出现的次数。
2. 对于从 1 到 n 的每一个数字，我们需要计算它二进制表示中 1 的个数。具体算法是利用位运算 & 得到一个数的各位值，与值 1 相事实，如果结果是 1，则说明原来的数二进制表示中该位为 1，否则为 0。
3. 累加每个数字二进制表示中 1 的个数，最后就得到了从 1 到 n 中数字 1 出现的次数。

代码实现

以下是 C++ 代码的实现，具体注释已在代码中给出。

class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        long long factor = 1;
        int h, l, cur;  // h 为当前处理数位的高位，l 为当前处理数位的低位，cur 为当前处理的数位的值
        while (n / factor != 0) {
            h = n / (factor * 10);
            cur = (n / factor) % 10;  // 当前处理的数位
            l = n - (n / factor) * factor;  // 获取当前处理数位的低位值
            if (cur == 0) {
                count += h * factor;  // 在当前位为 0 时，计算数字 1 出现的次数
            } else if (cur == 1) {
                count += h * factor + l + 1;  // 在当前为为 1 时，计算数字 1 出现的次数
            } else {
                count += (h + 1) * factor;  // 在当前位大于 1 时，计算数字 1 出现的次数
            }
            factor = factor * 10;  // 更新处理的数位
        }
        return count;
    }
};

以上代码的时间复杂度为 $O(\log n)$。

数的二进制表示中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

示例 1

输入: 11
输出: 3
解释: 数字 11 的二进制为 1011，其中有三个 1。

实现思路

对于一个二进制数，如果该数的二进制表示中有 $k$ 个 1，则该数字与数字 $2^{k-1}$ 做与运算后的结果为 0。这是因为 $2^{k-1}$ 的二进制表示中只有一个 1，这个 1 对应到与它相交运算的另一个数的二进制表示中也只会有一个 1。

因此，我们可以利用这个方法来计算一个数的二进制表示中 1 的个数。具体实现思路是，从低位到高位依次判断每一位是否为 1，如果是则计数器加 1，同时将该数与当前所在的位数对应的 $2^n$ 值做与运算，判断是否等于 0，如果相等则结束循环。

代码实现

以下是 C++ 代码的实现，具体注释已在代码中给出。

class Solution {
public:
    int numberOf1(int n) {
        int count = 0;
        unsigned int flag = 1;  // 初始值是 1
        while (flag != 0) {
            if ((n & flag) != 0) {  // 判断当前位是否为 1
                count++;
            }
            flag = flag << 1;  // 更新对应的 $2^n$ 值 
        }
        return count;
    }
};

以上代码的时间复杂度为 $O(\log n)$。