给定一个整数 n，找到 1 到 n 范围内的异或
1 ^ 2 ^ 3 ^4 ^.....n 的异或；
暴力方法：
tc:o(n)
sc:o(1)
public int findexor(int n){
//naive/brute force approach:
int val = 0;
for(int i=1;i<5;i++){
val = val^ i;
}
return val;
}
最佳方法：
tc:o(1)
sc:o(1)
public int getexor(int n){
//better approach
/**
* one thing to observe is
* 1 = 001 = 1
* 1 ^2 = 001 ^ 010 = 011= 3
* 1^2^3 = 011 ^ 011 = 0= 0
* 1^2^3^4 = 000^100 = 100= 4
* 1^2^3^4^5 = 100^101 = 001= 1
* 1^2^3^4^5^6 = 001^110 =111= 7
* 1^2^3^4^5^6^7 = 111^111=000= 0
*
* what we can observer is :
*
* n%4==0 then result is: n
* n%4 ==1 then result is: 1
* n%4 ==2 then result is: n+1
* n%4==3 then result is: 0
*
* */
if(n%4==0) return n;
else if(n%4 ==1) return 1;
else if(n%4==2) return n+1;
else return 0;
}
如果我们必须找到 l 和 r 等范围之间的 异或怎么办
例如找到数字 4 和 7 之间的异或，即 4^5^6^7。
为了解决这个问题，我们可以利用与 getexor() 相同的最佳解决方案
首先我们将得到exor直到l-1，即getexor(l-1) = 1 ^ 2 ^ 3（因为l-1 = 3）……方程(1)
然后我们会发现 getexor(r) = 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ----equation(2)
最后，
result = equation(1) ^ equation(2)
= (1 ^ 2 ^ 3) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7)
= (4^5^6^7)
public int findExorOfRange(int L, int R){
return getExor(L-1) ^ getExor(R);
}
public int getExor(int N){
//better approach
/**
* one thing to observe is
* 1 = 001 = 1
* 1 ^2 = 001 ^ 010 = 011= 3
* 1^2^3 = 011 ^ 011 = 0= 0
* 1^2^3^4 = 000^100 = 100= 4
* 1^2^3^4^5 = 100^101 = 001= 1
* 1^2^3^4^5^6 = 001^110 =111= 7
* 1^2^3^4^5^6^7 = 111^111=000= 0
*
* what we can observer is :
*
* N%4==0 then result is: N
* N%4 ==1 then result is: 1
* N%4 ==2 then result is: N+1
* N%4==3 then result is: 0
*
* */
if(N%4==0) return N;
else if(N%4 ==1) return 1;
else if(N%4==2) return N+1;
else return 0;
}
