Trong bài toán này, chúng ta có hai số nguyên L và R biểu thị một dãy. Nhiệm vụ của chúng ta là tìm xor của tất cả các phần tử trong phạm vi [L, R].
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào - L =3, R =6
Giải thích - 3 ^ 4 ^ 5 ^ 6 =
Để giải quyết vấn đề này, chúng ta sẽ tìm MSB của R. MSB của câu trả lời sẽ không lớn hơn R. Bây giờ, chúng ta sẽ tìm tính chẵn lẻ của số bit từ 0 đến MSB.
Bây giờ, để tìm số chẵn lẻ cho một bit thứ i, chúng ta có thể thấy rằng trạng thái của bit thứ i sẽ thay đổi trên mỗi 2 với số. Điều tương tự cũng xảy ra đối với tất cả bit thứ i được đặt trong phạm vi từ L đến R. Khi làm điều này, hai trường hợp phát sinh -
Trường hợp 1 (i! =0) - Kiểm tra bit thứ i của L. nếu nó được thiết lập, kiểm tra tính chẵn lẻ của số giữa L và L + 2i. Và nếu một bit thứ i của L được thiết lập, thì L là lẻ, thì số đếm là lẻ, ngược lại nó là chẵn. Bây giờ, chúng ta sẽ chuyển đến R và xác định tính chẵn lẻ của một số phần tử giữa R-2i và R và thực hiện theo cùng một phương pháp.
Tất cả các số nguyên còn lại không được xem xét vì chúng sẽ tạo ra số chẵn của một số nguyên có tập bit thứ i.
Trường hợp 2 (i =0) - ở đây, chúng ta sẽ phải xem xét trường hợp sau -
Trường hợp 2.1 - L và R đều là số lẻ, đếm số lượng số nguyên có tập bit thứ 0 sẽ là (R-L) / 2 + 1 .
Trường hợp 2.2 - Nếu không, số đếm sẽ làm tròn xuống một số (R-L + 1) / 2 .
Ví dụ
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
#include <iostream>
using namespace std;
int findMSB(int x) {
int ret = 0;
while ((x >> (ret + 1)) != 0)
ret++;
return ret;
}
int XOREleInRange(int L, int R) {
int max_bit = findMSB(R);
int mul = 2;
int ans = 0;
for (int i = 1; i <= max_bit; i++) {
if ((L / mul) * mul == (R / mul) * mul) {
if (((L & (1 << i)) != 0) && (R - L + 1) % 2 == 1)
ans += mul;
mul *= 2;
continue;
}
bool oddCount = 0;
if (((L & (1 << i)) != 0) && L % 2 == 1)
oddCount = (oddCount ^ 1);
if (((R & (1 << i)) != 0) && R % 2 == 0)
oddCount = (oddCount ^ 1);
if (oddCount)
ans += mul;
mul *= 2;
}
int zero_bit_cnt = zero_bit_cnt = (R - L + 1) / 2;
if (L % 2 == 1 && R % 2 == 1)
zero_bit_cnt++;
if (zero_bit_cnt % 2 == 1)
ans++;
return ans;
}
int main(){
int L = 1, R = 4;
cout<<"The XOR of all element within the range ("<<L<<", "<<R<<") is : "<<XOREleInRange(L, R);
return 0;
} Đầu ra
The XOR of all element within the range (1, 4) is : 4