alice-bob-and-xor

Bob has just learned bit manipulation and is very excited about it. He goes to his friend Alice to show off his skills who is new to programming, and thus Bob challenges Alice to solve the following problem. Given two positive integers L and R, find L ^ (L+1) ^ (L+2) ^ ....... ^ (R-1) ^ R.

Alice needs to answer k such queries.
Since Alice is new to programming, she seeks your help.

NOTE: Here a^b represents XOR of 2 numbers a and b.

Input Format :
The first line contains a number k, the number of queries.
Each of the next k lines, contain two positive integers L and R.

Output Format:
For each query, output a single line, the required answer.

Constraints:

1 ≤ k ≤ 10^5

1 ≤ L ≤ R ≤ 10^9

SAMPLE INPUT
2
2 3
3 5

SAMPLE OUTPUT
1
2

Explanation

For the first query, 2^3 = 1

For the second query, 3^4^5 = 2

Difficulty: EASY

Starter code:

Solutions:
import random
def x(n):
	if n%4 == 0:
		return n
	if n%4 == 1:
		return 1
	if n%4 == 2:
		return n+1
	return 0

#for i in xrange(18):
t= int(input())
#inputfile.write(str(t)+'\n')
for j in range(t):
	#a = random.randint(1,15)
	#b = random.randint(a,15)
	#b = a-1
	#print a,b
	#inputfile.write(str(a)+" "+str(b)+'\n')
	a,b = list(map(int,input().split(' ')))
	# print a,b
	print(x(b)^x(a-1))


'''
This problem is easily solved if pattern of XOR operations is observed carefully.
The function 'help_xor' calculates the XOR total run from [0,a], if we look at following
table of 4-bit numbers: 0000 -- 0  [a]
	0001 -- 1  [1]
	0010 -- 3  [a+1]
	0011 -- 0  [0]
	0100 -- 4  [a]
	0101 -- 1  [1]
	0110 -- 7  [a+1]
	0111 -- 0  [0]
	1000 -- 8  [a]
where the first column is binary representation and then the decimal result and its relation to
its index(a) into the XOR list. As all upper bits cancel and the lowest two bits cycle every 4.
So, for range[l,r]; we can use 'help_xor' to find XOR for [0,b] and [0,a-1]. Since any value XOR'd
to itself is 0, the 'help_xor(l-1)' just cancels out all the values in XOR run less than 'l',
leaving with the XOR of range[l,r].
'''

def help_xor(a):
    res = [a, 1, a + 1, 0]
    return res[a % 4]


for t in range(int(input())):
    l, r = [int(x) for x in input().split()]
    print((help_xor(r) ^ help_xor(l - 1)))


arr=[]

def xor(x,y):
	arr1=[x-1,1,x,0]
	arr2=[y,1,y+1,0]
	x1=arr1[int((x-1)%4)];
	x2=arr2[int(y%4)];
	arr.append(x1^x2)


T=eval(input())
for i in range (1,T+1):        
	str=input()
	#X=input()
	N, X = str.split()
	xor(int(N),int(X))
	
	
for i in arr:
	print(i)


def f(x):
	a=[x, 1, x+1, 0]
	return a[x%4]

T=input()
for i in range(0, int(T)):
	x=input().split()
	L=int(x[0])
	R=int(x[1])
	print(f(R)^f(L-1))



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def f(n):
	if n%4 == 0: return n
	if n%4 == 1: return 1
	if n%4 == 2: return n+1
	return 0
	
t = int(input())
while t > 0:
	L, R = list(map(int, input().split()))
	print(f(R) ^ f(L-1))
	t -= 1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def cyanide(a):
	res=[]
	res.append(a)
	res.append(1)
	res.append(a+1)
	res.append(0)
	return res[a%4]


def Xor(a,b):
    return cyanide(b)^cyanide(a-1)


k=eval(input())
for i in range(k):
	m,n=input().split(' ')
	m=int(m)
	n=int(n)
	print(Xor(m,n))


def f(a):
	res=[]
	res.append(a)
	res.append(1)
	res.append(a+1)
	res.append(0)
	return res[a%4]

if __name__=='__main__':
	T = int(input())
	for i in range(T):
		M,N=list(map(int,input().split()))
		print(f(N)^f(M-1))


def find_xor_0(value):
	no = (value)%4
	xor = 0
	while no >=0:
		xor = xor^value
		value=value-1
		no = no-1
	return xor

T = eval(input())
for x in range(T):
	L, R = list(map(int,input().strip().split(' ')))
	print((find_xor_0(L-1)^find_xor_0(R)))







k  = int(input())
for i in range (0 , k ):
	str = input().split(" ");
	a = int(str[0]);
	b = int(str[1]);
	a=a-1;
	if (a&1) :
		temp = 1;
	else: 
		temp = a;
	
	xor_a = (a >> 1) & 1 ^ temp;

	if (b&1) :
		temp = 1;
	else: 
		temp = b;
	xor_b = (b >> 1) & 1 ^ temp;
	print((xor_b^xor_a));


def f(a):
	z=a%4
	if z==0:
		return a
	elif z==1:
		return 1
	elif z==2:
		return a+1
	else:
		return 0
			
t=int(input())
while t>0:
	t=t-1
	l_r=list(map(int,input().split()))
	x=f(l_r[0]-1)
	y=f(l_r[1])
	print(x^y)


def f(a):
	res = [a, 1, a+1, 0]
	return res[a%4]

t = int(input())
i = 0
while(i < t):
	n, m = list(map(int, input().split()))
	print(f(m) ^ f(n-1))
	i = i + 1



#xor repeats pattern after every 4th iteration
def xornum(n):
	if n%4 == 0:
		return n
	elif n%4 == 1:
		return 1
	elif n%4 == 2:
		return n+1
	elif n%4 == 3:
		return 0
	
def calculate(a,b):
	xorA = xornum(a-1)
	xorB = xornum(b)
	val =xorA ^ xorB
	print(val)
	
queries = int(input())
counter=0
while counter < queries:
	LL=[int(x) for x in input().split(' ')]
	L=LL[0]
	R=LL[1]
	calculate(L,R)
	counter += 1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def xor(a):
	res = [a, 1, a+1, 0]
	return res[a%4]

t = int(input())
while t>0:
	a, b = [int(i) for i in input().split()]
	print(xor(b) ^ xor(a-1))
	t -= 1


def f(n): return [n,1,n+1,0][n%4]

def solve(m,n):
	return f(m-1)^f(n)

t = int(input())
for i in range(t):
	m,n = list(map(int,input().split()))
	print(solve(m,n))


import sys

k=int(input());
while(k>0):
	a,b=list(map(int, sys.stdin.readline().split(" ")));
	
	if((a-1)%4==3):
		vala=0
	elif((a-1)%4==1):
		vala=1
	elif((a-1)%4==2):
		vala=a
	else:
		vala=a-1
	if((b)%4==3):
		valb=0
	elif((b)%4==1):
		valb=1
	elif((b)%4==2):
		valb=b+1
	else:
		valb=b
  
	print(vala^valb)
	
	k-=1
		
		
	
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def findxor(num):
	ret = []
	ret.append(num)
	ret.append(1)
	ret.append(num+1)
	ret.append(0)
	return ret[num%4]
t = eval(input())
t = int(t)
for i in range(t):
	n=input()
	n=n.split()
	l = int(n[0])
	h = int(n[1])
	print(findxor(h)^findxor(l-1))
	



def xor(n):
	lst = [n,1,n+1,0]
	res = lst[n%4]
	return res
k = int(input())
for i in range(k):
	l,r = list(map(int,input().split()))
	print(xor(l-1) ^ xor(r))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def myfun(start):
	mlist = [start, 1, start+1, 0]
	return mlist[start%4]

for _ in range(int(input())):
	start, end = list(map(int, input().split()))
	print(myfun(end) ^ myfun(start - 1))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''



size=int(input())	
for j in range(0,size):
	inp=list(map(int,input().split()))
	L=inp[0]
	R=inp[1]
	res=L
	mod=R%4
	temp=1
	if mod==0:
		temp=R
	elif mod==1:
		temp=1
	elif mod==2:
		temp=R+1
	else:
		temp=0
	
	mod1=(L-1)%4
	temp1=1
	if mod1==0:
		temp1=L-1
	elif mod1==1:
		temp1=1
	elif mod1==2:
		temp1=L
	else:
		temp1=0	
		
	print(temp^temp1)	


import sys

test = int(sys.stdin.readline())
for i in range(test):
	a, b = list(map(int,sys.stdin.readline().strip().split()))
	val = 0
	l = b+1-a
	if a%2==0 and l%4==0:
		sys.stdout.write("0\n")
	elif a%2==0:
		for j in range(b+1-l%4,b+1):
			val^=j
		sys.stdout.write(str(val)+"\n")
	elif a%2==1 and (l-1)%4==0:
		sys.stdout.write(str(a)+'\n')
	else:
		for j in range(b+1-((l-1)%4),b+1):
			val^=j
		sys.stdout.write(str(val^a)+"\n")


def sumof(a):
	k=[a,1,a+1,0]
	return k[a%4]

def sumxor(a,b):
	return sumof(a-1)^sumof(b)


for _ in range(eval(input())):
	a,b=list(map(int,input().split()))
	print(sumxor(a,b))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name

f(n) = 1^2^...^n = (0^1)^(2^3)^(4^5)...^(n?) = 1^1^1^...^(n?)
= 0 if n = 4k+3
= 1 if n = 4k+1
= n+1 if n = 4k+2
= n if n = 4k
'''
k = int(input())
while k > 0:
	l, r = input().split()
	l = int(l)
	r = int(r)
	l = l-1
	
	if r%4 == 3:
		xorb = 0
	elif r%4 == 1:
		xorb = 1
	elif r%4 == 2:
		xorb = r+1
	else:
		xorb = r
		
	if l%4 == 3:
		xora = 0
	elif l%4 == 1:
		xora = 1
	elif l%4 == 2:
		xora = l+1
	else:
		xora = l
	
	ans = xorb ^ xora
	#print(xora)
	#print(xorb)
	print(ans)
	
	k = k-1
	
	
		


tc=int(input())

def findXor(a):
	arr=[a,1,a+1,0]
	return arr[a%4]
for i in range(tc):
	l,r=list(map(int , input().split()))
	print(findXor(r)^findXor(l-1))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math
k=eval(input())
while(k>0):
	k=k-1
	x,y=list(map(int,input().split()))
	x=x-1
	if(x%2==0):
		x1=(x>> 1) & 1 ^ x
	else:
		x1=(x >> 1) & 1 ^ 1
	if(y%2==0):
		y1=(y >> 1) & 1 ^ y
	else:
		y1=(y >> 1) & 1 ^ 1
	print(x1^y1)
		
		


cases = int(input())
res =0

def fun(s):
	mylist=[s,1,s+1,0]
	return mylist[s%4]

for i in range(cases):
	start,end = input().split(' ')
	start = int(start)
	end   = int(end)
	res =  fun(end)^fun(start-1)

#	tmp = start
#	tmp2 = start + 1
#	while tmp2 <= end:
#		res = tmp^tmp2
#		tmp = res
#		tmp2 = tmp2 +1
	print(res)


k  = int(input())
for i in range (0 , k ):
	str = input().split(" ");
	a = int(str[0]);
	b = int(str[1]);
	a=a-1;
	if (a&1) :
		temp = 1;
	else: 
		temp = a;
	
	xor_a = (a >> 1) & 1 ^ temp;

	if (b&1) :
		temp = 1;
	else: 
		temp = b;
	xor_b = (b >> 1) & 1 ^ temp;
	print((xor_b^xor_a));


from sys import stdin
raw_input = stdin.readline

def result(n):
	x = n / 4 * 4
	ans = x
	for i in range(x + 1, n + 1):
		ans ^= i
	return ans
	
for q in range(int(input())):
	a, b = list(map(int, input().split()))
	print(result(a - 1) ^ result(b))