How to find XOR of all the elements in given range?

general
, , , ,
1

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll Xor(ll n)
{
	if(n%4==0)
	return n;
	if(n%4==1)
	return 1;
	if(n%4==2)
	return n+1;
	if(n%4==3)
	return 0;
}
int main() 
{
	ll t;
	cin>>t;
	while(t--)
	{
	 ll l,r;
	 cin>>l>>r;
	 if(l==r)
	 cout<<"0\n";
	 else
	 cout<<abs(Xor(r)-Xor(l-1))<<"\n";	 
	} 
	
	return 0;
}
2

@vijju123 pls help me

3

xor is done in between the elements . You cannot find the correct of an element . In the range you can find the xor of element using ^ operator.

4

@trashmaster
it can be done directly ,You can refer this

5

Nice . Thanks for the link .

6

You need to output Xor(r) ^ Xor(l-1) and not Xor(r) - Xor(l-1), because xor is its own inverse.

2 Likes
7

I think you conceptually are in a doubt with xor.

Lets say I have a xor numbers till 8 in xor(8) and numbers till 5 in xor(5).

xor(8)=1^2^3^4^5^6^7^8
xor(5)=1^2^3^4^5

Now, lets say you want xor of all numbers in range [6,8] , i.e. 6^7^8.

What does xor do? If the bits are same, it will result in 0, if the bits are different, it results in 1.

xor(5)=1 , xor(8)=8.

Their difference is 7. But whats their xor?

8=1000
1=0001
A=1001//A=ans=9.

You can see that the anser of 6^7^8 is indeed 9. Meaning, xor®^xor(l-1) can be greater than r itself, so only “^” operator should be used. You cannot replace “^” with a simple “-” or “+” sign.

(PS: I assume that @meooow 's answer already clarified the doubt of “Xor of a number with itself is always 0”)

8

Please don’t use the award points feature, you will end up decreasing your own reputation points!
I don’t even know why it exists without any guidelines for use -_-

2 Likes
9

Forget that, even some people from CC team dont know why it exists XD

10

OK , thanks for informing!!