题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。每组数据输入$n(1 \leq n \leq 10^{18})$。

定义$popcount(x)$为$x$二进制中的$1$的个数。

输出$popcount(0 \oplus 1) + popcount(1 \oplus 2) + popcount(2 \oplus 3) + … + popcount((n-1) \oplus n)$。

其中$\oplus$表示异或。

输入样例

5
5
7
11
1
2000000000000

输出样例

8
11
19
1
3999999999987

算法

打表找规律

说来惭愧，没有总结出很好的结论，只是通过打表找到了规律。$1$第一次出现是在$1$位置，然后每隔$1$个位置出现一次；$3$第一次出现是在$2$位置，然后每隔$3$个位置出现一次；$7$第一次出现是在$4$位置，然后每隔$7$个位置出现一次，……

这样就发现规律了，$num$在$start$位置第一次出现，然后每$offset$个数会有一个。初始化$num=1$，$start=1$，$offset=2$，$num$的出现次数为$1+\lfloor \frac{n-start}{offset} \rfloor$，其中$\lfloor . \rfloor$表示对$.$向下取整。接下来倍增$start$和$offset$，自增$num$，直到$start$超过$n$。

复杂度分析

时间复杂度

$start$从$1$倍增到超过$n$，整个算法就能够结束，而对于每个$start$，内部的计算都是$O(1)$的。因此，算法整体的时间复杂度为$O(log_2n)$。

空间复杂度

整个算法过程仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int T;
LL n;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n);
        LL num = 1, start = 1, offset = 2, ans = 0;
        while(start <= n) {
            LL cnt = 1 + (n - start) / offset;
            ans += cnt * num;
            num++;
            start <<= 1;
            offset <<= 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}