题解 | #格雷码#

思路：
预处理出所有2的次幂的答案
显然有如下递推式：

void init() {
    sz[0] = 1;
    for (int i = 1; i <= 32; i++) {
        sz[i] = 2 * sz[i - 1] + 1;
    }
}

其实sz[i]的本质含义是在0-i-1位都是0的情况，翻转第i位（可能是0变1，也可能是1变0）的最少操作次数

考虑输入的数其二进制表示中“1”的奇偶性。
不妨来看2个例子（下列数为二进制表示）：
100100， 1000100100
我们发现，前一个例子中，在翻转100000的过程中，会出现100100这一步（即相当于翻转了第2位）（感兴趣的朋友可以认真推推我们是怎么预处理2次幂答案，怎么有那个递推式的）
所以100100的答案为 翻转第5位的答案 - 翻转第2位的答案
而第二个例子：
1000100100
在翻转1000000000的过程中，会出现1000100000这一步，而1000100000这一步则相当于1000100100翻转了第2位。
所以答案为 翻转第2位的答案 + 翻转9位的答案 - 翻转第5位的答案。
一般的，我们记录输入数二进制表示中1的个数。
若为奇数，则在二进制表示中，从右往左枚举出现1的位数，依次为+答案 -答案 +答案......
反之则为-答案 +答案 -答案.......
代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll sz[32]; 
void init() {
    sz[0] = 1;
    for (int i = 1; i <= 32; i++) {
        sz[i] = 2 * sz[i - 1] + 1;
    }
}
ll n;
ll cnt;
ll tmp;
ll arr[32];
ll ans;
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    init();
    cin >> n;
    while (n) {
        if (n & 1) {
            arr[++cnt] = tmp;
        }    
        tmp ++;
        n >>= 1;
    }
    if (cnt & 1) {
        for (int i = 1; i <= cnt; i += 2) {
            ans += sz[arr[i]];
        }
        for (int i = 2; i <= cnt; i += 2) {
            ans -= sz[arr[i]];
        }
    }
    else {
        for (int i = 2; i <= cnt; i += 2) {
            ans += sz[arr[i]];
        }
        for (int i = 1; i <= cnt; i += 2) {
            ans -= sz[arr[i]];
        }        
    }
    cout << ans << "\n";
    return 0;
}