Constraints
Time Limit: 1 secs, Memory Limit: 256 MB
Description
Given two integers S and F, what is the XOR (exclusive-or) of all numbers between S andF (inclusive)?
Input
The first line of input is the integer T, which is the number of test cases (1 ≤ T ≤ 1000). Tlines follow, with each line containing two integers S and F (1 ≤ S ≤ F ≤ 1 000 000 000).
Output
For each test case, output the (decimal) value of the XOR of all numbers between S and F, inclusive.
Sample Input
53 105 513 42666 13371234567 89101112
Sample Output
8539089998783
Problem Source
2014年每周一赛第八场
题意：计算区间[S,F]所有整数的异或和。
思路：先讨论S==1时的情况：若F为奇数，则看F/2是否为奇数，若是则结果为0，否则为1；若F为偶数，则看F/2是否为奇数，若是则结果为F+1，否则为F。
S^...^F == (1^...^F) ^ (1^...^(S - 1))
1 // Problem#: 11598 2 // Submission#: 3058633 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University 6 #include7 using namespace std; 8 int main() 9 {10 int t,s,f,ss,ff;11 scanf("%d",&t);12 while(t--)13 {14 scanf("%d%d",&s,&f);15 if(f&1)ff=!((f>>1)&1);else ff=f+((f>>1)&1);16 s--;17 if(s&1)ss=!((s>>1)&1);else ss=s+((s>>1)&1);18 printf("%d\n",ff^ss);19 }20 return 0;21 }
今天又研究出另一种解法：
先来观察一组二元序列：
00，01，10，11；
100，101，110，111；
1000，1001，1010，1011；
……
可见每组元素的异或和一定为0，即只要F的二进制表示以11结尾，那么区间[0,F]内所有整数的异或和一定为0.
于是有下面这个公式：
设sumofxor(x)为区间[0,x]内所有整数的异或和，则有
1 // Problem#: 11598 2 // Submission#: 3063400 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University 6 #include7 using namespace std; 8 int sumofxor(int x) 9 {10 int i,j,s;11 for(i=0;i<=3;i++)12 if((x & 0x3) == i)13 {14 s = 0;15 for(j=3-i;j>=1;j--)s ^= (x + j);16 return s;17 }18 return 0;19 }20 int main()21 {22 int t,s,f;23 scanf("%d",&t);24 while(t--)25 {26 scanf("%d%d",&s,&f);27 printf("%d\n",sumofxor(f) ^ sumofxor(s-1));28 }29 return 0;30 }