home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

XOR ของทุกตัวเลขในช่วง [L, R] ใน C++

โจทย์

ได้รับจำนวนเต็ม 2 จำนวน L และ R แทนช่วง ต้องการหา XOR ของทุกตัวเลขในช่วง [L, R] รวมทั้งสองข้าง

ตัวอย่าง

Input: L = 3, R = 6
Output: 3 ^ 4 ^ 5 ^ 6 = 4

วิธีแก้ปัญหา

ใช้คุณสมบัติของ XOR แบบ bit-by-bit:

  1. หา MSB (Most Significant Bit) ของ R - คำตอบจะไม่มีบิตสูงกว่านี้
  2. สำหรับแต่ละ bit position i (จาก 1 ถึง MSB) ตรวจสอบ parity (คี่/คู่) ของจำนวนครั้งที่ bit นั้นเป็น 1 ในช่วง [L, R]
  3. Bit i จะสลับสถานะทุก 2i ตัวเลข
  4. คำนวณ parity สำหรับแต่ละ bit แยกกัน แล้วรวมผลลัพธ์

กรณีพิเศษ: Bit 0 (LSB)

  • กรณี L และ R คี่ทั้งคู่: จำนวน = (R - L) / 2 + 1
  • กรณีอื่น: จำนวน = floor((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++) {
        // ตรวจสอบว่า L และ R อยู่ในบล็อก 2^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 = false;
        // ตรวจสอบ L
        if (((L & (1 << i)) != 0) && (L % 2 == 1)) oddCount = !oddCount;
        // ตรวจสอบ R
        if (((R & (1 << i)) != 0) && (R % 2 == 0)) oddCount = !oddCount;
        
        if (oddCount) ans += mul;
        mul *= 2;
    }
    
    // Bit 0 (LSB)
    int 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

วิธีแก้ง่ายกว่า (XOR Prefix)

ใช้คุณสมบัติ: XOR(1..n) มี pattern ซ้ำทุก 4 ตัว:

int xor1toN(int n) {
    switch (n % 4) {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        case 3: return 0;
    }
    return 0;
}

int rangeXOR(int L, int R) {
    return xor1toN(R) ^ xor1toN(L - 1);
}

วิธีนี้ง่ายกว่า เร็วกว่า และเข้าใจง่ายกว่ามาก แนะนำให้ใช้วิธีนี้แทน

สรุป

การหา XOR ในช่วง [L, R] สามารถทำได้ใน O(1) ด้วย XOR prefix pattern หรือ O(log R) ด้วย bit-by-bit analysis วิธี prefix pattern แนะนำให้ใช้ในทางปฏิบัติ