要算 $\sum_{i=0}^{n}\mathrm{Cnt}(\mathrm{Rev}(i)+i)$，反过来按位统计：对每一位 $b$，数一数有多少个 $i\le n$ 使得 $\mathrm{Rev}(i)+i$ 的第 $b$ 位是 $1$，加起来就是答案。

关键在于 $i+\mathrm{Rev}(i)$ 的进位结构。设 $i$ 的二进制长度为 $m$，$\mathrm{Rev}$ 把第 $j$ 位搬到第 $m-j+1$ 位，所以

$(i+\mathrm{Rev}(i))$ 的第 $j$ 位，只由「第 $j$ 位与第 $m-j+1$ 位」这一对、以及从更低位的进位决定。

于是把 $i$ 的位从两端配对，从最低位那一对开始逐对做数位 DP。处理到第 $i$ 对（第 $i$ 位配第 $m-i+1$ 位）时，状态里要记：

• 进位：这一对相加后往下一对传的进位，以及这一对自身产生的 $1$ 的个数；
• 比较关系：已经把两端的位定下来之后，$i$ 与 $\mathrm{Rev}(i)$ 谁更大（三种：小于/等于/大于），后面确定「还贴着 $n$ 的上界」的那部分时要用；
• 上界：高半部分是否还顶在 $n$ 的对应位上（顶住了就不能随便填 $1$）。

DP 里同时维护两个量：方案数和已经统计到的 $1$ 的个数之和。转移时新增的 $1$ 的个数乘上方案数累加进去，这样最后得到的就是「所有合法 $i$ 的位数之和」。逐位统计与整体统计是一回事，因为每一位的贡献都能在配对到它时结算。

$n$ 的位数是 $m$，还要把长度 $1,2,\dots,m-1$ 的 $i$（即二进制全是 $1$、且长度不足 $m$）单独用同样的 DP 累加一遍。

复杂度 $O(m^2)$ 级别（状态里那个「$1$ 的个数」一维只到 $m$）。

#include <cstdio>
#include <cstring>
#define N 55
#define LL long long

int m;          // n 的二进制位数
int dgt[N + 1]; // n 的二进制位，dgt[1] 是最低位
int lmt[N + 1]; // 这一轮用的上界，lmt[1] 是最低位
LL ans;

// f[第几步][进位][上一个「对位和不为 1」的位置][它的值][是否已经小于上界][低位与上界的比较]
LL f[N][2][N][3][2][3];
LL sum[N][2][N][3][2][3]; // 同一状态里「已经算出的那部分答案」之和

// 把所有「二进制长度恰为 len、且不超过 lmt[1..len]」的 v 的
//   Σ popcount(v + Rev(v)) = Σ ( 2 * popcount(v) - 做加法产生的进位个数 )
// 一次算出来。做法是把 v 的位从两端配对，从最低的一对开始逐对确定。
LL calc(int len) {
    int step = (len + 1) / 2;             // 配对的步数
    int tp = (len & 1) ? step - 1 : step; // 反向清点进位时要看到的最大下标
    memset(f, 0, sizeof f);
    memset(sum, 0, sizeof sum);
    f[0][0][0][0][0][1] = 1; // 进位 0；还没碰到对位和不为 1 的位；贴着上界；低位相等
    for (int j = 1; j <= step; j++) {
        int hi = len - j + 1, lo = j; // 这一步要确定的两条位
        for (int c = 0; c < 2; c++) {
            for (int p = 0; p <= step; p++) {
                for (int v = 0; v < 3; v++) {
                    for (int a = 0; a < 2; a++) {
                        for (int b = 0; b < 3; b++) {
                            LL k = f[j - 1][c][p][v][a][b];
                            LL acc = sum[j - 1][c][p][v][a][b];
                            if (!k) continue;
                            for (int h = 0; h < 2; h++) {
                                if (j == 1 && h == 0) continue; // 最高位必须是 1
                                int na;
                                if (a || h < lmt[hi]) {
                                    na = 1; // 已经松了，或这一位比上界小 ⇒ 低位随便填
                                } else if (h == lmt[hi]) {
                                    na = 0; // 还贴着上界
                                } else {
                                    continue; // 贴着还填大了 ⇒ v > n，整条砍掉
                                }
                                if (hi == lo) {
                                    // 正中间那一位，自己和自己配对
                                    int ps = h + h, nc = (ps + c) >> 1;
                                    LL add = ps - nc;
                                    if (ps == 2) add -= (step - 1) - p; // 反向那半里的进位个数
                                    int nv = ps ? 2 : 1;
                                    f[j][nc][j][nv][na][b] += k;
                                    sum[j][nc][j][nv][na][b] += acc + k * add;
                                } else {
                                    for (int l = 0; l < 2; l++) {
                                        int ps = h + l, nb;
                                        if (l < lmt[lo]) {
                                            nb = 2;
                                        } else if (l > lmt[lo]) {
                                            nb = 0;
                                        } else {
                                            nb = b;
                                        }
                                        int nc = (ps + c) >> 1;
                                        LL add = 2 * ps - nc;
                                        int np = p, nv = v;
                                        if (ps != 1) {
                                            if (ps == 2) add -= j - p;
                                            np = j;
                                            nv = ps ? 2 : 1;
                                        }
                                        f[j][nc][np][nv][na][nb] += k;
                                        sum[j][nc][np][nv][na][nb] += acc + k * add;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    LL res = 0;
    for (int c = 0; c < 2; c++) {
        for (int p = 0; p <= step; p++) {
            for (int v = 0; v < 3; v++) {
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 3; b++) {
                        if (!a && !b) continue; // 贴着上界、低位又更大 ⇒ v 超过上界
                        LL k = f[step][c][p][v][a][b];
                        LL acc = sum[step][c][p][v][a][b];
                        if (!k) continue;
                        LL cut = 0;
                        if (v == 2 && tp > p) cut = tp - p;
                        res += acc - k * cut;
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    // freopen("rev.in", "r", stdin);
    // freopen("rev.out", "w", stdout);
    LL n;
    scanf("%lld", &n);
    LL t = n;
    while (t) {
        dgt[++m] = (int)(t & 1);
        t >>= 1;
    }
    for (int len = 1; len < m; len++) {
        for (int i = 1; i <= len; i++) lmt[i] = 1; // 长度不足 m 的 v 必定不超过 n，上界按全 1 算
        ans += calc(len);
    }
    for (int i = 1; i <= m; i++) lmt[i] = dgt[i]; // 长度恰为 m 的 v 要不超过 n
    ans += calc(m);
    printf("%lld\n", ans);
    return 0;
}