Permutation XOR Sum solution codechef

For a permutation $P$ of integers from $1$ to $N$ , let’s define its value as $(1 \oplus P_{1}) + (2 \oplus P_{2}) + \dots + (N \oplus P_{N})$ .

Given $N$ , find the maximum possible value of the permutation of integers from $1$ to $N$ .

As a reminder, $\oplus$ denotes the bitwise XOR operation

The first line of the input contains a single integer $T$ $-$ the number of test cases. The description of test cases follows.

The only line of each test case contains a single integer $N$ .

For each test case, output the maximum possible value of the permutation of integers from $1$ to $N$ .

Subtask 1 (60 points): The sum of $N$ over all test cases doesn’t exceed $10^{6}$ . Subtask 2 (40 points): No additional constraints.

0
6
6
20
841697449540506

For $N = 1$ , the only such permutation is $P = (1)$ , its value is $1 \oplus 1 = 0$ .

For $N = 2$ , the permutation with the best value is $P = (2, 1)$ , with value $1 \oplus 2 + 2 \oplus 1 = 6$ .

For $N = 3$ , the permutation with the best value is $P = (2, 1, 3)$ , with value $1 \oplus 2 + 2 \oplus 1 + 3 \oplus 3 = 6$ .

For $N = 4$ , the permutation with the best value is $P = (2, 1, 4, 3)$ , with value $1 \oplus 2 + 2 \oplus 1 + 3 \oplus 4 + 4 \oplus 3 = 20$ .

For Solution