给一个整数，计算从零到数字的异或值

Question

count "0 xor 1 xor 2 xor......xor N"，例如，我给数字 3 作为 N，程序应该 return 0，现在我把我的代码放到在线junge，结果是time limt exceed，我很难找到错误在哪里，谁能给我一些建议，在此先感谢。

 long long xorSum(long long  x) {   
   long long j =0;//we supposed x is big enough ,less than 10^18.
   for (long long i=1 ;i<=x;i++) {
     j  ^= i;
   }
    return j;
  }

Answer 1

简单的逻辑，复杂度为 O(1)

long long xorSum(long long k) {
    switch (k % 4) {
        case 0: return k;
        case 1: return 1;
        case 2: return k + 1;
        case 3: return 0;
    }
}

证明，归纳法：从1到4，很容易看出逻辑是正确的。假设上面的逻辑一直正确到一个数x，也就是x % 4 = 3，那么当前和为0。

从x + 1 which (x + 1) % 4 = 0开始，所以二进制表示总是xxx00（xxx代表任意二进制数），所以xor最后一个和，也就是0我们会得到 xxx00.
下一个数字的形式为 xxx01 -> 异或运算将为 xxx00 xor xxx01 = 00001。
从 xxx01 到 xxx10 -> xor 将是 00001 xor xxx10 = xxx11
从 xxx10 到 xxx11 -> xor 将是 xxx11 xor xxx11 = 00000 -> 注意 xxx11 % 4 = 3 重新启动整个序列并完成证明。

给一个整数，计算从零到数字的异或值

give an integer number ,count the xor value from zero to the number

c++

algorithm

xor