Giá trị XOR lớn nhất của một cặp từ một phạm vi trong C++

Đề bài

Cho một phạm vi [L, R], chúng ta cần tìm hai số nguyên trong phạm vi này sao cho XOR của chúng là lớn nhất trong tất cả các cặp có thể chọn.

Nếu phạm vi cho là L = 1 và R = 21 thì đầu ra sẽ là 31 vì 31 là XOR của 15 và 16 và đó là giá trị lớn nhất trong phạm vi.

Thuật toán

1. Tính giá trị (L^R)
2. Từ bit quan trọng nhất của giá trị này, thêm tất cả các bit 1 để có kết quả cuối cùng

Ví dụ

#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 << "Kết quả = " << getMaxXOR(L, R) << endl;
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên, nó tạo ra đầu ra sau:

Kết quả = 31