Giá trị XOR tối đa của một cặp từ một dải ô trong C ++

Tuyên bố vấn đề

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 số tất cả các lựa chọn có thể có của hai số nguyên

Nếu phạm vi đã cho là L =1 và R =21 thì đầu ra sẽ là 31 vì −31 là XOR là 15 và 16 và nó là lớn nhất trong phạm vi.

Thuật toán

1. Calculate the (L^R) value
2. From most significant bit of this value add all 1s to get the final result

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 << "Result = " << getMaxXOR(L, R) << endl;
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Result = 31