Đố vui về thuật toán xử lý bít

chắc cái này đáp án là R/2 hoặc (R-L)/2 hay chia 4 chia 1 gì đó

viết cách giải phải viết mảng tam giác 2 chiều, mất công lắm nên thôi vậy

A[0] = 0
A[1] = 1 xor 0 = 1
A[2] = 2 xor 1 = 3
A[3] = 3 xor 3 = 0
A[4] = 4 xor 0 = 4
A[5] = 5 xor 4 = 1
A[6] = 6 xor 1 = 7
A[7] = 7 xor 7 = 0
A[8] = 8 xor 0 = 8
A[9] = 9 xor 8 = 1
A[10] = 10 xor 1 = 11
A[11] = 11 xor 11 = 0
A[12] = 12 xor 0 = 12
A[13] = 13 xor 12 = 1

:v
=> Từ dãy trên thấy a ^ b = 1 khi a % 4 = 1 (1, 5, 9)
Và tiếp đó a % 4 = 2 = a ^ 1
a % 4 = 3 -> a ^ a = 0
và a % 4 = 0 -> a ^ 0 = a

R = 411662880
R % 4 = 0 ->
Output của dãy trên = R?? :v

Cách làm của mình cũng giống vậy.

xét hàm xor(n) = 0 ^ 1 ^ 2 ... ^ n

xor=lambda n:[n,1,n+1,0][n%4]

Chứng minh quy luật:

• n=0 hàm xor đúng
• n = 4*k , do kết quả của phép xor trước = 0 nên 0^n=n
• n= 4*k+1, do kết quả trước đó là (4*k) nên phép (4*k)^(4*k+1) chỉ khác nhau bit cuối cùng nên kết quả =1
• n=4*k+2, các số trước có kq =1 , n chẵn nên bit cuối = ‘0’ phép xor làm tăng kết quả lên 1 đơn vị = 4*k+3
• n=4*k+3, các số trước = 4*k+3 ^ n = 0

Từ đó có kết quả bài toán:

xor=lambda n:[n,1,n+1,0][n%4]
ans=xor(R) ^ xor(L-1)

Đây là thuật toán của nó:
long gx(long n) {
switch (++n & 7) {
case 0: case 7: return 0;
case 1: case 2: return n-1;
case 3: case 4: return 2;
case 5: case 6: return n+1;
}
return -1;
}

int main() {
int t;
long l, r;
cin >> t;
do {
cin >> l >> r;
cout << (gx® ^ gx(l-1)) << endl;
} while (–t);
return 0;
}