ในปัญหานี้ เราได้รับเลขจำนวนเต็ม L และ R สองตัวที่แสดงถึงช่วง งานของเราคือค้นหา xor ขององค์ประกอบทั้งหมดภายในช่วง [L, R]
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − L=3, R =6
คำอธิบาย − 3^4^5^6 =
ในการแก้ปัญหานี้ เราจะหา MSB ของ R โดย MSB ของคำตอบจะไม่เกิน R ตอนนี้ เราจะพบความเท่าเทียมกันของการนับจำนวนบิตตั้งแต่ 0 ถึง MSB
ในการหาจำนวนพาริตีสำหรับบิต ith เราจะเห็นว่าสถานะของบิต ith จะเปลี่ยนในทุกตัวเลขที่ 2 เหมือนกันสำหรับบิตทั้งหมดที่ตั้งไว้ในช่วง L ถึง R ในการทำเช่นนี้ จะเกิดสองกรณี -
กรณีที่ 1(i !=0) − ตรวจสอบบิตของ L หากตั้งค่าไว้ ให้ตรวจสอบการนับความเท่าเทียมกันของตัวเลขระหว่าง L และ L+2i และหากตั้งค่าบิต ith ของ L แล้ว L จะเป็นเลขคี่ การนับจะเป็นเลขคี่ ไม่เช่นนั้น จะเป็นเลขคู่ ตอนนี้ เราจะย้ายไปที่ R และกำหนดความเท่าเทียมกันของการนับจำนวนองค์ประกอบระหว่าง R-2i และ R แล้วทำตามวิธีเดียวกัน
ส่วนที่เหลือทั้งหมดจะไม่ถูกพิจารณาเนื่องจากจะสร้างจำนวนเต็มด้วยชุดบิต ith
กรณีที่ 2(i =0) − ที่นี่ เราจะต้องพิจารณากรณีต่อไปนี้ -
กรณีที่ 2.1 − L และ R ทั้งคู่เป็นเลขคี่ ให้นับจำนวนเต็มด้วยชุดบิตที่ 0 จะเป็น (R-L)/2+1 .
กรณีที่ 2.2 − มิฉะนั้น การนับจะถูกปัดเศษเป็นตัวเลข (R-L+1)/2 .
ตัวอย่าง
โปรแกรมแสดงการใช้งานโซลูชันของเรา
#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;
} ผลลัพธ์
The XOR of all element within the range (1, 4) is : 4
