CountTotalSetBits.cpp

/* GFG
You are given a number N. Find the total count of set bits for all numbers from 1 to N(both inclusive).

Example 1:

Input: N = 4
Output: 5
Explanation:
For numbers from 1 to 4.
For 1: 0 0 1 = 1 set bits
For 2: 0 1 0 = 1 set bits
For 3: 0 1 1 = 2 set bits
For 4: 1 0 0 = 1 set bits
Therefore, the total set bits is 5.
Example 2:

Input: N = 17
Output: 35
Explanation: From numbers 1 to 17(both inclusive), 
the total number of set bits is 35.

Your Task: The task is to complete the function countSetBits() that takes n as a parameter and returns the count of all bits.

Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ N ≤ 10^8

*/

class Solution{
    public:
    // n: input to count the number of set bits
    //Function to return sum of count of set bits in the integers from 1 to n.
    int countSetBits(int n)
    {
        // Your logic here
        int ans=0;
        for(int i=1;i<=31;i++)
        {
            int p_div=pow(2,i);
            int p_mul=p_div/2;
            int temp=(n+1)/p_div;
            ans+=(temp*p_mul);
            int r=(n+1)%p_div;
            if(r>p_mul)
                ans+=(r-p_mul);
            if(temp==0)
                break;
        }
        return ans;
    }
};