Count numbers have all 1s together in binary representation in C++

We are given a positive integer N. The goal is to count the numbers less than or equal to N that have all 1’s in their binary representation. For example 1 is 1, 3 is 11, 7 is 111, 15 is 1111... so on.

If we see the numbers then all of them are 2i-1. Where i start from 1. To check such numbers less than n. We’ll compare if 2i-1<=n. Then increment count.

Let’s understand with examples.

Input − N=15

Output − Number having all 1's in binary : 4

Explanation − Numbers as sum of same primes − The numbers will be 1 3 7 15

Input − N=50

Output − Number having all 1's in binary : 5

Explanation − Numbers as sum of same primes −

Approach used in the below program is as follows

• We take a positive integer N..

• Function allOnes(int n) takes n as input and returns the numbers that have all 1’s in binary representation.

• Take the initial variable count as 0 for such numbers..

• Traverse from i=1 to i<=n using for loop.

• For each i, if pow(2,i)-1 is less than or equal to n. Increment count.

• Return the count as a result at the end of the for loop.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int allOnes(int n){    int count = 0;    for(int i=1;i<=n;i++){       if(n>=pow(2,i)-1){          count++;          //cout<<" "<<pow(2,i)-1;       }    }    return count; } int main(){    int N=23;    cout <<endl<< "Number having all 1's in binary : "<<allOnes(N);    return 0; }

Output

If we run the above code it will generate the following output −

Number having all 1's in binary : 4