Maximum XOR value of a pair from a range in C++

Problem statement

Given a range [L, R], we need to find two integers in this range such that their XOR is maximum among all possible choices of two integers

If the given range is L = 1 and R = 21 then the output will be 31 as − 31 is XOR of 15 and 16 and it is maximum within range.

Algorithm

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

Example

#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; }

Output

When you compile and execute the above program. It generates the following output −

Result = 31