如何快速求 1 到 n 的异或结果？

简化版

1 ^ 2 ^ ... ^ n 有 4 个一组的周期规律。根据 n % 4 判断：余 0 返回 n，余 1 返回 1，余 2 返回 n + 1，余 3 返回 0。这个结论常用于区间异或、缺失数字变体和“只出现一次”类题的推导，时间 O(1)，空间 O(1)。

详细版

int xor1ToN(int n) {
    switch (n & 3) {       // 等价于 n % 4
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        default: return 0;
    }
}

int rangeXor(int l, int r) {
    return xor1ToN(r) ^ xor1ToN(l - 1);
}

异或前缀 f(n)=1^2^...^n 呈现长度为 4 的周期。
区间 [l,r] 的异或可以用前缀抵消：f(r) ^ f(l-1)。
这个技巧不是每个题单都会单独列题，但在位运算追问中很高频。

完整版教学

一、为什么 1 到 n 的异或会有规律

异或有抵消性质，但 1..n 并不是成对相同的数字，所以不能直接说都消掉。规律来自二进制低位翻转周期，尤其是连续整数每 4 个一组时异或结果会回到 0。

先手算前几个前缀：

f(1)=1
f(2)=1^2=3
f(3)=1^2^3=0
f(4)=1^2^3^4=4
f(5)=4^5=1
f(6)=1^6=7
f(7)=7^7=0
f(8)=0^8=8

你会看到结果按 n,1,n+1,0 的结构循环，只是要按 n % 4 分情况。

二、四种余数情况怎么来的

把连续 4 个数写成 4k, 4k+1, 4k+2, 4k+3。重点观察一组的异或：

4k ^ (4k+1) ^ (4k+2) ^ (4k+3) = 0

例如：

4 ^ 5 ^ 6 ^ 7
= 100 ^ 101 ^ 110 ^ 111
= 000

所以每完整 4 个数会抵消成 0，最后只看尾巴剩几个数。于是：

n % 4	f(n)
0	n
1	1
2	n + 1
3	0

记忆钩子：异或前缀四步一循环，余数口诀是 0->n, 1->1, 2->n+1, 3->0。

三、为什么可以用 `n & 3` 代替 `n % 4`

当除数是 2 的幂时，取模可以用低位掩码表示。4 的二进制是 100，一个数对 4 取模只取决于最低 2 位，因此：

n % 4 == n & 3
3 = 0b11

例如 14 = 1110，最低两位是 10，所以 14 & 3 = 2，14 % 4 = 2。在现代编译器里 %4 通常也会被优化，写 n & 3 更多是表达位运算思维。

四、区间异或如何由前缀抵消得到

设 f(n)=1^2^...^n，那么：

f(r)     = 1 ^ 2 ^ ... ^ (l-1) ^ l ^ ... ^ r
f(l - 1)= 1 ^ 2 ^ ... ^ (l-1)
f(r) ^ f(l-1) = l ^ (l+1) ^ ... ^ r

因为前面相同的 1..l-1 出现两次会抵消。例子：求 [5,8] 的异或。

f(8)=8
f(4)=4
range = 8 ^ 4 = 12
校验：5 ^ 6 ^ 7 ^ 8 = 12

这个前缀思想和前缀和类似，只是加减换成了异或抵消。

五、它和缺失数字有什么联系

缺失数字可以看成“理论全集异或实际数组”。如果理论全集是 0..n，可以用循环异或，也可以用 xor1ToN(n) 先得到全集异或，再异或数组所有元素。

int x = xor1ToN(n);
for (int v : nums) x ^= v;
return x;

不过在 LeetCode 268 中，直接循环 x=n; x^=i; x^=nums[i] 更常见，因为代码不需要额外写前缀函数。前缀异或规律更适合区间异或追问。

六、复杂度与适用边界

求 1..n 前缀异或只看 n mod 4，所以时间 O(1)，空间 O(1)。区间异或调用两次前缀函数，也仍然是 O(1)。

如果 n=0，通常定义 xor1ToN(0)=0，这样 rangeXor(1,r) 的公式也自然成立。若题目包含负数连续区间，就不能直接套这个周期，因为固定宽度补码和无限数学整数的语义要先定义清楚。

七、常见误区与追问

误区：认为连续整数异或一定为 0。 只有完整的 4 个一组会抵消，尾巴不同结果不同。
误区：把余数表记成 0->0。 n%4==0 时结果是 n，例如 1^2^3^4=4。
误区：区间异或写成 f(r)-f(l-1)。 异或前缀靠 ^ 抵消，不是用减法。
追问：为什么 n & 3 等价于 n % 4？ 对 2 的幂取模只由低若干位决定，4 需要最低 2 位。
追问：0..n 的异或怎么求？ 因为 0 不影响异或，所以 0^1^...^n 等于 1^...^n。
追问：这个规律能推广到取模 8 吗？ 具体前缀异或周期仍是 4，不是因为取模 4 本身，而是连续整数异或的低位翻转规律形成了 4 周期。

八、加强记忆

1..n 异或前缀记住 4 种情况：n%4=0 返回 n，1 返回 1，2 返回 n+1，3 返回 0。区间 [l,r] 用 f(r)^f(l-1)，因为相同前缀异或两次会抵消。这个技巧常作为缺失数字、区间异或和位运算追问的加分点。

简化版

详细版