其实这是我真正意义上的第一次不看题解作出的绿题，因为我做题前总会把题解先扫一遍看看难不难。
解题思路
先将完整的数统一处理，再处理剩余部分。
比方说 x=25：
0110111001011101111000100。
为方便处理，直接丢掉第一位。再通过位数进行分割。
\color{red}1\color{blue}1011\color{green}100101110111\color{purple}1000\color{black}100。
分析一下具体的分割过程：
- 割下 1 位数，共有 2^{1-1}=1 个数，每个数有 1 位，一共 1\times2^{1-1}=1 位。还剩 24-1=23 位。
- 割下 2 位数，共有 2^{2-1}=2 个数，每个数有 2 位，一共 2\times2^{2-1}=4 位。还剩 23-4=19 位。
- 割下 3 位数，共有 2^{3-1}=4 个数，每个数有 3 位，一共 3\times2^{3-1}=12 位。还剩 19-12=7 位。
- 割下 4 位数，由于剩下的数小于 4\times2^{4-1}=32 位，所以无法完全分割。只能割下 \lfloor\frac{7}{4}\rfloor=1 个数，还剩 7\bmod 4=3 位。
这一部分的代码如下：
x--;
int i;
for (i = 0; ; i++) {
if (x < (i + 1) * (1ll << i)) break;
x -= (i + 1) * (1ll << i);
res += (1ll << i);
}
res += x / (i + 1);
x %= (i + 1);
所以一共分割出了 1+2+4+1=8 个数。
我们先处理这 8 个数，再将剩下的 3 个数单独处理。
现在的任务是求 \operatorname{popcount} 的前缀和。
部分内容借鉴自该博客，如侵删。
如果我们把二进制下的 0 至 15 的数全部列出来，找一下规律：
分开观察一下每一行，可以发现每一行 0 的个数和 1 的个数都相等！
这是因为如果 n 的二进制下第 k 位数是 1 的话，那么有 \dfrac{n\bmod2^k}{2^{k-1}}\ge1，也就是说，n\bmod2^k\ge2^{k-1}。可以发现，它正好是占一半的。
所以 \sum\limits_{i=0}^{2^k-1}\operatorname{popcount}(i)=\dfrac{k\times2^k}{2}=k\times2^{k-1}。
那么对于一个任意的正整数 n，如何计算 \sum\limits_{i=0}^{n}\operatorname{popcount}(i) 呢。考虑拆位计算贡献的方式，下面以 n=22=(10110)_2 为例：
- 最高位为 1，统计 (00000)_2 至 (01111)_2。共对答案产生了 4\times2^{4-1}=32 的贡献。
- 第三高位为 1，统计 (10000)_2 至 (10011)_2，共对答案产生了 1\times2^2+2\times2^{2-1}=8 的贡献。
- 第四高位为 1，统计 (10100)_2 至 (10101)_2，共对答案产生了 2\times2^1+1\times2^{1-1}=5 的贡献。
最后还要统计 \operatorname{popcount}(n)，所以答案为 32+8+5+3=48。
为方便处理，可以直接将 n 增加 1 在进行计算，最后就不用统计 \operatorname{popcount}(n) 了。
这个部分的代码如下：
int getsum(int x) {
int res = 0, cnt = 0;
x++;
while (x) {
if(x & 1) res += (cnt * (1ll << (cnt - 1))) + (1ll << cnt) * popcount(x >> 1);
x >>= 1;
cnt++;
}
return res;
}
现在我们已经处理完了完整部分，接下来我们处理剩余部分。
还是分析我们的事例，最后剩下 3 位。可以发现，这个数就是下一个数的前三位。
我们如何计算 n 的前 k 位？首先我们计算 n 的二进制位数，也就是 \lfloor\log_2n\rfloor。我们可以将后 \lfloor\log_2n\rfloor-k+1 位直接删去。这样留下来的就是前 k 位了。最后我们对它求一遍 \operatorname{popcount} 即可。
于是我们就做完了这道题。
本篇题解共有 3703 字符（包含这句话）。
AC 代码
别问我这是什么语言。
#include <bits/stdc++.h>
#define int long long/*
'''
*/
using namespace std;
int x, res;
int popcount(int x) {
int res = 0;
while (x) {
res += x & 1;
x >>= 1;
}
return res;
}
int getsum(int x) {
int res = 0, cnt = 0;
x++;
while (x) {
if(x & 1) res += (cnt * (1ll << (cnt - 1))) + (1ll << cnt) * popcount(x >> 1);
x >>= 1;
cnt++;
}
return res;
}
signed main() {
cin >> x; x--;
int i;
for (i = 0; ; i++) {
if (x < (i + 1) * (1ll << i)) break;
x -= (i + 1) * (1ll << i);
res += (1ll << i);
}
res += x / (i + 1);
x %= (i + 1);
cout << getsum(res) + popcount(res + 1 >> (int)log2l(res + 1) - x + 1);
return 0;
}
/*
'''
def popcount(x):
res = 0;
while x:
res += x & 1;
x >>= 1;
return res;
def getsum(x):
res = 0;cnt = 0;
x += 1;
while x:
if x & 1:
if cnt >= 1:res += cnt * (1 << (cnt - 1)) + (1 << cnt) * popcount(x >> 1);
else:res += (1 << cnt) * popcount(x >> 1);
x >>= 1;
cnt += 1;
return res;
x = int(input())
x -= 1;
res = 0;i = 0;
while True:
if x < (i + 1) * (1 << i):break
x -= (i + 1) * (1 << i);
res += (1 << i);
i += 1;
res += x // (i + 1);
x %= (i + 1);
ans = getsum(res) + popcount((res + 1) >> ((res + 1).bit_length() - x));
print(ans);
# */