Tính Tổng A[i] XOR A[j] - Programming - Dạy Nhau Học

Trang chủ » Xor Lập Trình » Tính Tổng A[i] XOR A[j] - Programming - Dạy Nhau Học

Có thể bạn quan tâm

Code khá tường minh đó. Khổ nỗi bị sai :smile:.

Bạn để ý rằng, trong 1 dãy xor, cứ có chẵn bit 1 thì kết quả của dãy bằng 0, nếu không thì bằng 1.

1 ^ 1 ^ 1 = 1 1 ^ 1 ^ 1 ^ 1 = 0

Cái gì xor 0 cũng bằng chính nó.

x ^ 0 = x

Ta sẽ sử dụng 2 tính chất trên vào bài này.

Lưu ý thêm, a[i] ^ ... ^ a[j] = 1 số ghép bởi các bit, với mỗi bit k là kết quả của phép xor bit thứ k của các số a[i],... a[j], hay

res là 1 số có nhiều bit, với mọi bit k thì res[k] = a[i][k] ^ ... ^ a[j][k]

Dòng trên không đúng về mặt lập trình, tuy nhiên mình sử dụng để bạn có thể mường tượng dễ hơn.

Limit bài này là 10^6 nên ta xét 20 bit. Với 20 bit, ta kiểm tra với mỗi bit i có bao nhiêu số a[u] có giá trị của bit i bằng 1. Các bit được đánh số từ phải sang trái. Bit 0 là bit tận cùng bên phải. Ví dụ:

a[1] = 10 = 0..001010 (2) // bit 1 và bit 3 bằng 1 a[2] = 8 = 0..001000 (2) // bit 3 bằng 1 a[3] = 7 = 0..000111 (2) // bit 0, 1, 2 bằng 1 a[4] = 18 = 0..010010 (2) // bit 1 và bit 4 bằng 1 a[5] = 3 = 0..000011 (2) // bit 0 và bit 1 bằng 1 -------------------------- XOR = 0..010100 (2) // thử xor cả dãy

author’s note: đến đây mình phát hiện ra code này không đẹp lắm, hơn nữa lại rất dễ gây hiểu nhầm, mình sẽ giải thích theo cách của mình.

Ta định nghĩa

b[i] = số lượng các số a[u] có bit i bằng 1

Cách kiểm tra xem số a[u] có bit i bằng 1 hay không:

// nhớ khởi tạo mảng b !!!!!!!!! for (int i = 0; i <= 20; i++) // chạy từ 0 -> 20 không sao cả for (int u = 0; u < n; u++) if (a[u] & (1 << i) > 0) b[i]++; // toán tử bitwise AND

1 << i là pow(2, i), nó biểu diễn dưới dạng nhị phân là 100..00 (i chữ số 0). Xem ví dụ để hiểu dòng code trên hơn:

x = 10 (1010 trong hệ nhị phân) -> lấy bit 3 x = 1010 & (1 << 3) = 1000 ------------------- 1000 // 1 & 1 = 1, các trường hợp khác cho kết quả = 0 hết. Khi kết quả x & (1 << 3) lớn hơn 0, ta kết luận x có bit 3 bằng 1.

Ta đã xong mảng b. Trích xuất kết quả:

s = 0; // khởi tạo biến kết quả !!!!!! for (int i = 0; i <= 20; i++) // lấy 20 bit if (b[i] % 2 == 0) // ở vị trí bit i có chẵn bit 1 -> bit i của kết quả sẽ bằng 0 s += 0; // mình rảnh thôi, bạn có thể bỏ dòng này đi else // ở vị trí bit i có lẻ bit 1 -> bit i của kết quả sẽ bằng 1 s += (1 << i)

Bạn nên đọc 1 tài liệu về bitwise để hiểu thêm.

Từ khóa » Xor Lập Trình