Q:

Find total set bits from 0 to (2^n) - 1

Let us define F(n) as 
F(n) = total set bits in binary representation of 0 to (2^n) -1. 

Eg:

F(1) = number of bits set in 0 + number of bits set in 1 = 1
F(2) = number of bits set in 0 + ...... number of bits set in 3 = 4

Is there a O(log n) algorithm to calculate F(n) where n can be as large as 10^6. 

A:

If you are asking for the number of bits set in the binary representations of all the integers from 0 to 2n–1, it's simple:

There are n bits in such a number. 
There are 2n such numbers. 
Each place-value is set in exactly half the numbers of the set. 
The number of set bits is half the number of total bits. 
The number of set bits is n × 2n ÷ 2 = n × 2n–1. 

Please remember to cite this webpage in your homework :v) .