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

8
5
39
0
89998783

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\n",ff^ss);
19     }
20     return 0;
21 }                                 

SOJ - 11598

原文：http://www.cnblogs.com/gangduo-shangjinlieren/p/4041760.html