I Wanna Beat the Joke

我们定义f(n)为前n个数中关系左侧首次出现的数的数量。
可得f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 3。
以n=4为例，前四个数中首次出现的是1、2、3，而4并非首次出现
(因为n = 1时1 ⊨ 4已经出现4)。
易知题目所求即为2 * f(n)。
可以得到递推关系：f(n) = 总数 - 非首次出现的数 = n - f(n / 4)。
“非首次出现的数”为f(n / 4)是因为这些数都是之前“首次出现的数”乘 4 得到的。
f(n)可以通过递归或者迭代实现计算，时间复杂度为log(n)。

递归：

def f(x):
    if x == 0:
        return 0
    return x - f(x // 4)
for _ in range(int(input())):
    n = int(input())
    print(2 * f(n))

迭代：

def f(x):
    op = 1
    res = 0
    while x:
        if op:
            res += x
        else:
            res -= x
        x >>= 2
        op ^= 1
    return res
 
for _ in range(int(input())):
    n = int(input())
    print(2 * f(n))