SOJ

11598. XOR

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

5
3 10
5 5
13 42
666 1337
1234567 89101112

Sample Output

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 #include<bits/stdc++.h>
 7 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
",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 #include<bits/stdc++.h>
 7 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
",sumofxor(f) ^ sumofxor(s-1));
28     }
29     return 0;
30 }