学步园

（我在这里参与讨论了下异或算法的相关问题，写下来作为备忘）

 

总结和证明一下1^2^3^...^N的速算公式：

不难证明以下两个异或公式(简要起见在此不作证明)：
0^N = N
N^N = 0

所以有：
1^2^...^N = 0^1^2^...^N
即只要得出0^1^2^...^N的速算公式即为1^2^...^N的公式

又因为：
0^1^2^3 的二进制形式为：
0^1^10^11 = 0
4^5^6^7的二进制形式为：
100^101^110^111 = 0
(即：0^1^2^3^4^5^6^7 = 0)
根据异或的运算规则（相同为0，不同为1）及二进制的特性(每4位即可使二进位中的01交换一次，请自行试验)可知，0^1^2^...^N中从0开始每隔4位即会出现一个结果0

现假设运算至第i位时得到结果0，即：
0^1^...^i = 0
且
(i+1)%4=0
即只要(i+1)%4=0则：
0^1^...^i = 0
也就有：
0^1^...^i^(i+1) = i+1 (因为：0^N = N)

根据以上总结速算方法（用程序表示了，实测在N比较大时能提高不少效率）：

    public static int GetXorValue(int N){
        
        if(N%4==0) return N;
        
        if(N<4)
        {
            int result=N;
            for(int i=1;i<N;i++)
            {
                result = result^i;
            }
            return result;
        }
        else
        {
            switch(N%4)
            {
                case 1:
                    return (N-1)^N;
                case 2:
                    return (N-2)^(N-1)^N;
                case 3:
                    return 0;
                default:
                    throw new Exception("Error");
            }
        }
    }