Johnny and Another Rating Drop
Contest: Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!
Difficulty rating: 1400
Tags: bitmasks, greedy, math

The last contest held on Johnny's favorite competitive programming platform has been received rather positively. However, Johnny's rating has dropped again! He thinks that the presented tasks are lovely, but don't show the truth about competitors' skills.

The boy is now looking at the ratings of consecutive participants written in a binary system. He thinks that the more such ratings differ, the more unfair is that such people are next to each other. He defines the difference between two numbers as the number of bit positions, where one number has zero, and another has one (we suppose that numbers are padded with leading zeros to the same length). For example, the difference of $$$5 = 101_2$$$ and $$$14 = 1110_2$$$ equals to $$$3$$$, since $$$0101$$$ and $$$1110$$$ differ in $$$3$$$ positions. Johnny defines the unfairness of the contest as the sum of such differences counted for neighboring participants.

Johnny has just sent you the rating sequence and wants you to find the unfairness of the competition. You have noticed that you've got a sequence of consecutive integers from $$$0$$$ to $$$n$$$. That's strange, but the boy stubbornly says that everything is right. So help him and find the desired unfairness for received numbers.

Input format:
The input consists of multiple test cases. The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases. The following $$$t$$$ lines contain a description of test cases.

The first and only line in each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^{18})$$$.

Output format:
Output $$$t$$$ lines. For each test case, you should output a single line with one integer — the unfairness of the contest if the rating sequence equals to $$$0$$$, $$$1$$$, ..., $$$n - 1$$$, $$$n$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For $$$n = 5$$$ we calculate unfairness of the following sequence (numbers from $$$0$$$ to $$$5$$$ written in binary with extra leading zeroes, so they all have the same length):

- $$$000$$$
- $$$001$$$
- $$$010$$$
- $$$011$$$
- $$$100$$$
- $$$101$$$

The differences are equal to $$$1$$$, $$$2$$$, $$$1$$$, $$$3$$$, $$$1$$$ respectively, so unfairness is equal to $$$1 + 2 + 1 + 3 + 1 = 8$$$.

Example input:
5
5
7
11
1
2000000000000

Example output:
8
11
19
1
3999999999987

Editorial:
Let us start by calculating the result for $$$n = 2^k$$$. It can be quickly done by calculating the results for each bit separately and summing these up. For $$$i$$$-th bit, the result is equal to $$$\frac{2^k}{2^{i}}$$$ as this bit is different in $$$d-1$$$ and $$$d$$$ iff $$$d$$$ is a multiple of $$$2^i$$$. Summing these up we get that the result for $$$n = 2^k$$$ is equal to $$$2^{k + 1} - 1 = 2n - 1$$$.
How to compute the answer for arbitrary $$$n$$$? Let us denote $$$b_1 > b_2 > \ldots > b_k$$$ as set bits in the binary representation of $$$n$$$. I claim that the answer is equal to the sum of answers for $$$2^{b_1}, 2^{b_2}, \ldots, 2^{b_k}$$$. Why?
We can compute results for intervals $$$[0, 2^{b_1}], [2^{b_1}, 2^{b_1} + 2^{b_2}], \ldots, [n - 2^{b_k}, n]$$$. We can notice that the result for interval $$$[s, s + 2^i]$$$, where $$$s$$$ is a multiple of $$$2^i$$$, is equal to the answer for $$$[0, 2^i]$$$ so we can just compute the results for intervals $$$[0, 2^{b_1}], [0, 2^{b_2}], \ldots, [0, 2^{b_k}]$$$!
This allows us to compute the answer for arbitrary $$$n$$$ in $$$\mathcal{O}(\log n)$$$ – just iterate over all bits $$$b$$$ and add $$$2^{b + 1} - 1$$$ if $$$b$$$ is set. Equivalently we can just write down $$$2n - \texttt{#bits set}$$$ as the answer.
Final complexity is $$$\mathcal{O}(t \log n)$$$.