Total set bits from 1-n

#1

Is there any way of counting total no of set bits from 1 to n in O(logn)??.

#2

Can you ellaborate with some example??

#3

like total no of set bits from 1-4 are 4
01->1
10->1
11->2
similarly from 1-7->12
so i have to count the total no of set bits from 1 to n in O(logn).

#4

Suppose you want the answer for 39=(100111).
Count number of bits in this. Let this be n=6.
Lets get the answer for n-1 i.e. 5. Number of set bits will be 5*2^4 or (n-1)*2^(n-2). This is because if we have 2^n, n bit numbers, then 2^(n-1) numbers will have ith bit set and 2^(n-1) numbers will have ith bit off, where i varies from 1 to n.
Now we have the count for n<=31. We want further count till 39.
num=num-2^(n-1).
So now we need answer for 39-32=7, and we have 7+1 numbers whose first bit will be set.
Get answer for num<=3, (2^1)*2=4.
num=7-4=3, and we have 3+1 numbers whose first bit will be set.

Similarly, ans is 52^4 + 8 + 2(2^1) + 4 + 1*(2^0) + 3…