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

Count total set bits.

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 ≤ 108

C++
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) { int c = 0; for (int p = 1; p <= n; p *= 2) { c += (((n + 1) / p) / 2) * p; if (((n + 1) / p) % 2) { c += (n + 1) % p; } } return c; } };

Python3
#User function Template for python3 class Solution: dp={} def findMSB(self, x): i=0 while(pow(2, i)<=x): i+=1 return i-1 def countSetBits(self, n): if (n <= 1): return n elif n in self.dp: return self.dp[n] x = self.findMSB(n) self.dp[n]=(x * pow(2, (x - 1))) + (n - pow(2, x) + 1) + self.countSetBits(n - pow(2, x)) return self.dp[n]