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