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

[hoang1379 (Nguyễn Hải Hoàng)]

Mình mới đọc được 1 bài toán về xử lý bit khá hay đăng lên đây cho anh em chém nhé, mình cũng ko nghĩ ra được thuật toán đâu đọc của người ta thôi
Cho 1 mảng A được tạo theo công thức sau
A[0]=0
A[x]=A[x-1] XOR x
INPUT: cho 2 số nguyên là L=101268166 và R=411662880 là index của mảng
OUTPUT: giá trị của biểu thức A[L] XOR A[L+1] XOR … XOR A[R]
gợi ý:
a xor a =0; a xor 0=a; a xor b = b xor a;
tìm mối liên hệ giưa a[0],a[0] xor a[1],a[0] xor a[1] xor a[2]…
OUTPUT: 511721703

[tntxtnt]

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

[drgnz]

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

[Gio (Gió)]

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)

[hoang1379 (Nguyễn Hải Hoàng)]

Đâ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;
}