Count Total Setbits

You are given a number N. Find the total number of setbits in the numbers from 1 to N.

• Time : O(lgn)
• Space : O(1)

class Solution{
public:
    int countBits(int n){
        if(n <= 1) return n;
        int lg = log2(n);
        int res = lg * (1<<(lg-1)) + n - (1<<lg) + 1;
        return res + countBits(n ^ (1<<lg));
    }
};