从 1 到 n 的二进制数的计数

Question

我想找出 1 到 n 之间的二进制（二进制）有效数字的个数。

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;
}

Answer 2

详情： 在每一步中，如果数字是一，那么我们将 2 加到我们拥有的数字的幂上。如果数字大于 1，则所有情况都可能出现该位数，我们也可以计算该数字本身并完全更改答案（-1 是因为我们不想计算 0）。

#include <iostream>

using namespace std;

int main()
{
    long long int n, res = 0, power = 1;
    cin >> n;

    while(n != 0) {
        int rem = n % 10;
        if (rem == 1) {
            res += power;
        } else if (rem > 1) {
            res = 2 * power - 1;
        }
        n /= 10;
        power *= 2;
    }
    cout << res;
    return 0;
}

从 1 到 n 的二进制数的计数

Count of binary numbers from 1 to n

c++

algorithm

binary