Help in bitmanipulation

1

the link to the problem is :

editorial says:

#include <bits/stdc++.h>
using namespace std;

long long G(long long x){
long long a = x % 8;
if(a == 0 || a == 1) return x;
if(a == 2 || a == 3) return 2;
if(a == 4 || a == 5) return x+2;
if(a == 6 || a == 7) return 0;
return 0;
}

int main(){
int q;
cin >> q;
while(q–){
long long l, r, ans;
cin >> l >> r;
ans = G(r)^G(l-1);
cout << ans << endl;
}
return 0;
}

i have read the discussions but
i couldn’t understand y we are calculating g(r)^g(l-1)
pls help me.

2

Maybe this will help.
XOR over a Range

1 Like
3

G( r ) gives answer of XOR from 1 to r
G( l-1 ) gives answers of XOR from 1 to l - 1

and we actually need XOR from l to r

you can check that

4 ^ 5 ^ 6 = ( 1 ^ 2 ^ 3 ) ^ ( 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 )

[since xor of same number will be 0]

5

[4,6]=arr[4]^arr[5]^arr[6] but not 4^5^6.here arr[n]=1^2^…^n.

6

even
XOR(4 , 6) = XOR ( XOR(1 , 3) , XOR(1 , 6 ) )
arr[4] ^ arr[5] ^ arr[6] = ( arr[1] ^ arr[2] ^ arr[3] ) ^ ( arr[1] ^ arr[2] ^ arr[3] ^ arr[4] ^ arr[5] ^ arr[6] )

1 Like