题解 | 小苯的最短路（位运算+数学）

猜的。

好了不开玩笑了。分析题目，可得任意两点间XOR下路径长度都不会小于它们XOR的结果。这是一个很显然的结果，因为XOR在位与位之间是独立的，且其定义为相同记为0，不同记为1。在本题中值相同的位显然已经最优了，不用考虑。考虑值不同的位(0/1或1/0)，我们不可能找到一个中间值使得这个代价在传递中更小(无论找1还是0，动手试试就明白了)。这是因为XOR本质上就是不进位加法，你不可能使用进位加法得出比XOR更小的和。

所以任意两点之间的最短XOR路径即位其XOR的值，原题转化为求 。考虑到从2开始，每对奇偶数在XOR意义下是共轭的(很好理解，每一对数只有末尾数字不一样)，且这样的每组数XOR在一起的结果为1。后面就转化为判奇偶的问题了，所有人应该都会，就不说了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=300005;
int n;
void solve() {
    cin>>n; int m=(n-1)%4;
    if(m==0) cout<<0<<'\n';
    if(m==1) cout<<n+1<<'\n';
    if(m==2) cout<<1<<'\n';
    if(m==3) cout<<n<<'\n';
} 
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // solve();
    int T; cin>>T; while(T--) solve();
    return 0;
}