设 $f(n) = \sum_{i=0}^{n} (i \oplus n-i)$。

如果 $n$ 为偶数。

重要观察：$i$ 与 $n-i$ 的奇偶性相同，因此：

$$\begin{align*} f(n) &= \sum_{i=0}^{n} (i \oplus n-i) \\ &= 2 \times\sum_{i=0}^{n} (\lfloor \frac{i}{2} \rfloor \oplus \lfloor \frac{n-i}{2} \rfloor) \end{align*}$$

向下取整对于奇偶和偶数的运算是不同的，因此将 $i$ 为奇数和偶数的情况分开：

$$\begin{align*} f(n) &= \sum_{i=0，为偶数}^{n} (i \oplus n-i) + \sum_{i=0，为奇数}^{n} (i \oplus n-i) \\ &= 2 \times\sum_{i=0，为偶数}^{n} (\frac{i}{2} \oplus \frac{n-i}{2}) + 2 \times\sum_{i=0，为奇数}^{n} (\frac{i-1}{2} \oplus \frac{n-i-1}{2}) \\ &= 2 \times\sum_{i=0}^{\frac{n}{2}} (i \oplus \frac{n}{2} - i) + 2 \times\sum_{i=0}^{\frac{n}{2}-1} (i \oplus \frac{n}{2}-1 -i) \\ &= 2f(\frac{n}{2}) + 2f(\frac{n}{2}-1) \end{align*}$$

如果 $n$ 为奇数。

重要观察：$i$ 与 $n-i$ 的奇偶性不同，因此：

$$\begin{align*} f(n) &= \sum_{i=0}^{n} (i \oplus n-i) \\ &= \sum_{i=0}^{n} [ 2 \times (\lfloor \frac{i}{2} \rfloor \oplus \lfloor \frac{n-i}{2} \rfloor) + 1 ] \end{align*}$$

依然对于 $i$ 奇偶分类：

$$\begin{align*} f(n) &= 2 \times \sum_{i=0}^{n} (\lfloor \frac{i}{2} \rfloor \oplus \lfloor \frac{n-i}{2} \rfloor) + n + 1 \\ &= 2 \times [\sum_{i=0,为奇数}^{n}(\frac{i-1}{2} \oplus \frac{n-i}{2}) + \sum_{i=0,为偶数}^{n}(\frac{i}{2} \oplus \frac{n-i-1}{2})] + n + 1 \end{align*}$$

中括号内两坨东西是对称、等价的。

$$\begin{align*} f(n) &= 2 \times 2 \times \sum_{i=0}^{\frac{n-1}{2}}(i \oplus \frac{n-i}{2} - i) + n + 1\\ &= 4 \times f(\frac{n-1}{2}) + n + 1\\ \end{align*}$$

初始化 $f(0) = 0$。
上述的递推可以使用记忆化递归实现。
需要写一个高精度。

但是，你要注意了，$ans = \sum_{i=1}^{n-1} (i \oplus n-i) = f(n) - 2n$。

代码实现

这是我熬到 12 点写出的高精度，希望大家喜欢。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef vector<int> BigInt;
map<BigInt, BigInt> f;

BigInt read(){
	string s;
	cin >> s;
	int len = (int)s.size();
	BigInt res(len, 0);
	for(int i = 0; i < len; i ++) res[len - i - 1] = s[i] - '0';
	return res;
}

void write(BigInt x){
	for(int i = (int)x.size()-1; i >= 0; i --){
		cout << x[i];
	}
}

BigInt tran(int x){
	if(x == 0) return BigInt(1, 0);
	BigInt res;
	while(x > 0){
		res.push_back(x%10);
		x/=10;
	}
	return res;
}

//加法

BigInt operator + (const BigInt &a, const BigInt &b){
	BigInt x = a, y = b;
	int len = (int)max(x.size(), y.size()) + 1;
	BigInt res(len, 0);
	x.resize(len), y.resize(len);
	for(int i = 0; i < (int)res.size() - 1; i ++){
		res[i] += x[i] + y[i];
		res[i+1] += res[i] / 10;
		res[i] %= 10;
	}
	while(res.back() == 0 && res.size() > 1){
		res.pop_back();
	}
	len = (int)res.size();
	while(res[len - 1] >= 10){
		res.push_back(res[len-1]/10);
		res[len-1] %= 10;
		len++;
	}
	return res;
}

BigInt operator + (const BigInt &x, const int &y){ return x + tran(y); }
BigInt operator + (const int &x, const BigInt &y){ return tran(x) + y; }


//减法
//默认 x >= y
BigInt operator - (const BigInt &a, const BigInt &b){
	int len = (int)max(a.size(), b.size())+1;
	BigInt res = a, y = b;
	res.resize(len), y.resize(len);
	for(int i = 0; i < len-1; i ++){
		if(res[i] < y[i]){
			res[i+1]--;
			res[i]+=10;
		}
		res[i] -= y[i];
	}
	while(res.size() > 1 && res.back() == 0){
		res.pop_back();
	}
	return res;
}


BigInt operator - (const BigInt &x, const int &y){ return x - tran(y); }
BigInt operator - (const int &x, const BigInt &y){ return tran(x) - y; }

//乘法
BigInt operator * (const BigInt &x, const BigInt &y){
	int len = (int)x.size() + (int)y.size();
	BigInt res(len, 0);
	for(int i = 0; i < (int)x.size(); i ++){
		for(int j = 0; j < (int)y.size(); j ++){
			res[i+j] += x[i] * y[j];
		}
	}
	while(res.size() > 1 && res.back() == 0){
		res.pop_back();
	}
	for(int i = 0; i < (int)res.size() - 1; i ++){
		res[i+1] += res[i]/10;
		res[i]%=10;
	}
	while(res[res.size()-1]>=10){
		len = (int)res.size();
		res.push_back(res[len-1]/10);
		res[len-1]%=10;
	}
	return res;
}

BigInt operator * (const BigInt &x, const int &y){ return x * tran(y); }
BigInt operator * (const int &x, const BigInt &y){ return tran(x) * y; }

//除法, 保证可以整除,且x > y
BigInt operator / (const BigInt &x, const int &y){
	BigInt res(x.size(), 0);
	int now = 0;
	for(int i = (int)x.size()-1; i >= 0; i --){
		now = 10*now + x[i];
		if(now >= y){
			res[i] = now/y;
			now%=y;
		}
	}
	while(res.back() == 0 && res.size() > 1){
		res.pop_back();
	}
	return res;
}

BigInt dfs(BigInt x){
	if(f.count(x)) return f[x];
	else if(x[0] % 2 == 1){
		return f[x] = 4 * dfs((x - 1) / 2) + x + 1;
	}else{
		
		return f[x] = 2 * dfs(x/2) + 2 * dfs(x/2-1);
	}
}

int main(){
	f[tran(0)] = BigInt(tran(0));
	BigInt n = read();
	write(dfs(n) - 2*n);
	return 0;
}