BITS  Counting Bits
Given N, if we write all numbers from 1 to N (both inclusive) in binary what is the count of 1s I have written.
For example, if N=3,
I will write down:
1
10
11
Therefore, a total of 4 ones.
Input Format:
First line contains, T, the number of testcases. Each testcase consists of one integer per line denoting N.
Output Format:
Print the required answer.
Constraints:
1 ≤ T ≤ 1000
1 ≤ N ≤ 1000
Sample Input:
1
3
Sample Output:
4
Problem Setter: Lalit Kundu
Solve harder version here: http://www.spoj.com/problems/BIT2
hide comments
ivar.raknahs:
20140222 15:34:55
easy with python 

Anubhav Balodhi :
20140216 08:38:12
The very basic of programming... 

Rishav Goyal:
20140213 04:50:55
try this after BITS , http://www.spoj.com/problems/BIT2 Last edit: 20140208 15:35:00 

Rishav Goyal:
20140213 04:50:55
would be better raise the limit ~10^9 or more than that. 

Aravindan Chandrasekaran:
20140213 04:50:55
But I am getting WA ? 

:
20140213 04:50:55
Last edit: 20140227 07:38:45 

Jacob Plachta:
20140213 04:50:55
I'm pretty sure that there are already problems on SPOJ that ask exactly this (or similar things), with larger bounds (like 10^9).


suryadev:
20140213 04:50:55
Anybody is having better solution than O(N) or O(NlogN) ? 

Bhavik:
20140213 04:50:55
@aravindan: yes 

Aravindan Chandrasekaran:
20140213 04:50:55
Answer for 1000 is 4938 right ? 
Added by:  darkshadows 
Date:  20140126 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 