Count Total Set Bits

 https://www.interviewbit.com/problems/count-total-set-bits/

    ans= (2^(x-1) * x)+ (n - 2^x +1 ) + solve(n - 2^x ) 

x= highest power of 2 (which is less than n) 

    #define MOD 1000000007

    #define ll long long int

ll largestpowerof2inrange(int n)

{

    int x=0;

    while((1 << x) <= n){

        x++;

    }

    return (x-1)%MOD;

}

int Solution::solve(int n) {

    if(n==0) return 0;

    ll x = largestpowerof2inrange(n);

    ll bittill2x=x*(1<<(x-1));

    ll msb= n-(1<<x)+1;

    ll rest=n-(1<<x);

    ll ans =  (bittill2x + msb + solve(rest))%MOD;

    return ans;

 

}