ค่า XOR สูงสุดของคู่จากช่วงใน C++

ข้อความของปัญหา

กำหนดช่วง [L, R] เราต้องหาจำนวนเต็มสองจำนวนในช่วงนี้ที่ XOR ของพวกเขาสูงสุดในทุกคู่ที่เป็นไปได้ของจำนวนเต็มสองจำนวน

ถ้าช่วงที่กำหนดคือ L = 1 และ R = 21 ผลลัพธ์จะเป็น 31 เพราะ 31 คือ XOR ของ 15 และ 16 และเป็นค่าสูงสุดในช่วง

อัลกอริทึม

1. คำนวณค่า (L^R)
2. จากบิตที่สำคัญที่สุด (MSB) ของค่านี้ ให้เพิ่มบิต 1 ทั้งหมดเพื่อให้ได้ผลลัพธ์สุดท้าย

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int getMaxXOR(int L, int R){
    int LXR = L ^ R;
    int msbPos = 0;
    while (LXR) {
        msbPos++;
        LXR >>= 1;
    }
    int maxXOR = 0;
    int two = 1;
    while (msbPos--) {
        maxXOR += two;
        two <<= 1;
    }
    return maxXOR;
}

int main(){
    int L = 1;
    int R = 21;
    cout << "Result = " << getMaxXOR(L, R) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้ -

Result = 31