Count of binary numbers from 1 to n-CodePudding

I want to find the number of numbers between 1 and n that are valid numbers in base two (binary).

1 ≤ n ≤ 10^9

For example, suppose n is equal to 101.

Input: n = 101

In this case, the answer is 5

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

Another example

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

Here is my code...

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

But I want more speed.
(With only one loop or maybe without any loop)

Thanks in advance!

CodePudding user response：

The highest binary number that will fit in a d-digit number d1 d2 ... dn is b1 b2 ... bn where

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

A trivial implementation using 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;
}

CodePudding user response：

Details: In each step, if the digit was one, then we add 2 to the power of the number of digits we have. If the number was greater than 1, then all cases are possible for that number of digits, and we can also count that digit itself and change the answer altogether (-1 is because we do not want to calculate the 0).

#include <iostream>

using namespace std;

int main()
{
    long long int n, res = 0, count_digit = 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;
}

CodePudding user response：

Basic Idea

Let your number be dn,...,d0, then the number of requested numbers is sum(ci*(2^i)), where c1 = 1, if di > 0 and 0 otherwise.

So, the code could look as follows.

Code

uint64_t countMatchingNumbers(uint64_t value) {
    uint64_t  num  = 0;
    uint64_t  powerOfTwo = 1;
    while (value > 0) {
        uint8_t digit = value % 10;

        if (digit > 0) {
            num  = powerOfTwo;
        }
        powerOfTwo <<= 1;
        value      /= 10;
    }

    return num;
}