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

Question

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.

Answer 1

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

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

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

Answer 2

I smell homework so Im leaving out code

A simple solution , using the fact that for the ith least significant bit, answer will be

(N/2^i)*2^(i-1)+ X
where X = N%(2^i) - (2^(i-1)-1) iff N%(2^i)>=(2^(i-1)-1)

Consider the ith least significant bit(1 based indexing) for numbers from 1 to N , then they repeat with a period equal to 2^i.And in the period , first half of the values are 0 and the next half are ones.For example :- For numbers from 0 to 7,(0 will contribute nothing so no effect)

000
001
010
011
100
101
110
111
1st least significant bit = 01010101 Period=2
2nd least significant bit = 00110011 Period=4
3rd least significant bit = 00001111 Period=8
and so on.

So for the ith least significant bit ,answer will be (N/Period)*(Half of Period Size) + (N%(2^i - 1) - Half of Period Size + 1)
The second term will only be taken when N%Remainder is greater than or equal to Half of Period Size.
Also , N%(2^i) can be written as N&(2^i - 1)

Courtesy : http://www.geeksforgeeks.org