c++ - 计算 1 到 n 的二进制数

Question

我想找到 1 到 n 之间以 2 为基数(二进制)的有效数字的数量。

1 ≤ n ≤ 10^9

例如，假设 n 等于 101。

Input: n = 101

在本例中，答案是 5

Output: 1, 10, 11, 100, 101 -> 5

另一个例子

Input: n = 13
Output: 1, 10, 11 -> 3

这是我的代码...

#include <iostream>

using namespace std;

int main()
{
    int n, c = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int temp = i;
        bool flag = true;
        while(temp != 0) {
            int rem = temp % 10;
            if (rem > 1)
            {
                flag = false;
                break;
            }
            temp /= 10;
        }
        if (flag)
        {
            c++;
        }
    }
    cout << c;
    return 0;
}

但我想要更快的速度。
(只有一个循环或可能没有任何循环)

提前致谢!

Answer 1

适合 d 位数字 d1 d2 ... dn 的最高二进制数是 b1 b2 ... bn 其中

bi = 0 if di = 0, and
bi = 1 otherwise.

使用 std::to_string 的简单实现:

int max_binary(int input) {
    int res = 0;
    auto x = std::to_string(input);
    for (char di : x) {
        int bi = x == '0' ? 0 : 1;
        res = 2 * res + bi;
    }
    return res;
}