XOR của tất cả phần tử trong khoảng [L, R] trong C++

Trong bài toán này, cho hai số nguyên L và R biểu diễn một khoảng. Nhiệm vụ là tìm XOR của tất cả các phần tử trong khoảng [L, R].

Ví dụ:

Input – L=3, R=6

Giải thích – 3^4^5^6

Để giải, ta tìm MSB (bit quan trọng nhất) của R. MSB của kết quả không lớn hơn R. Tìm chẵn/lẻ của số bit từ 0 đến MSB.

Để tìm chẵn/lẻ cho bit thứ i: trạng thái bit i thay đổi mỗi 2^i số. Có hai trường hợp:

Trường hợp 1 (i != 0) – Kiểm tra bit i của L. Nếu bit set, kiểm tra chẵn/lẻ giữa L và L+2^i. Nếu bit i của L set và L lẻ thì count lẻ, ngược lại chẵn. Tương tự với R.

Trường hợp 2 (i = 0) – Xét:

• 2.1 – L và R đều lẻ: count = (R-L)/2 + 1
• 2.2 – Ngược lại: count = floor((R-L+1)/2)

Ví dụ minh họa

#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 = (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 << "XOR của tất cả phần tử trong khoảng (" << L << ", " << R << ") là: " << XOREleInRange(L, R);
    return 0;
}

Kết quả

XOR của tất cả phần tử trong khoảng (1, 4) là: 4