背景

异或（xor，运算符号^）：按位计算，同0异1，1 ^ 0 = 1 ，1 ^ 1 = 0 ，如此。

现定义等差数列 1, 2, ... , n 的 异或和 为 f(n) = 1 ^ 2 ^ ... ^ n ，求f(n)的值。

实现

我们很容易想到质朴的实现如下：

1
2
3
4
5
6
7
int func(int n) {
    int xor_sum = 0;
    for (int i = 1; i <= n; ++i) {
        xor_sum ^= i;
    }
    return xor_sum;
}

时间复杂度O(n)，空间复杂度此处没有太大必要讨论。

通式

联想到等差数列的四则运算都是有求和公式的，那么异或运算有没有呢？直接这么看也看不出来，先输出个十来项看看规律：

1
2
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18};
// 1 3  0 4 1 7  0 8 1 11  0 12 1 15  0 16 1 19

注释中分别是从第1项到第18项的异或和。这个规律其实非常明显了，抛开前2个结果不看，后面4个为一组，定义为m组，通式如下：

1
2
3
4
// n=3, 0   n=7, 0      n=4m-1, 0
// n=4, 4   n=8, 8      n=4m, 4m
// n=5, 1   n=9, 1      n=4m+1, 1
// n=6, 7   n=10, 11    n=4m+2, 4m+3

从n>=3开始，后面的异或和的取值都是固定的常量或者公式求得。优化后实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int func(int n) {
    switch (n) {
        case 1: return 1;
        case 2: return 3;
        default:
            int r = n % 4;
            switch (r) {
                case 0: return r;
                case 1: return 1;
                case 2: return (n - 2) + 3;
                default: return 0;
            }
    }
}

时间复杂度O(1) ，部分代码为了体现公式没有精简，主要操作就是取余。

这样能提升不少性能。