Maximizing Xor

Maximizing Xor

Given a range [L, R] and find the maximal value of A xor B where L <= A <= B <= R.

Input:
L
R
Output:
the maximal value mentioned in the problem statement.
Example:
Input:
10
15
Output:
7

test

Solution

There are two methods intuitively:

  1. the basic one using two-level loop to search for the maximal value, which is very easy to implement but with bad performance and when the range is huge, it’s hard to solve within an ideal time;
  2. math technique to find out the underlying rules: remove the prefix same part and then set all the suffix to 1-bit. Actually if we remove the prefix with same bit then the left should be:
  • 0a1a2a3…
  • 1b1b2b3…
    and we are trying to get as many 1-bit as possible for each xor operation. There will be two cases: ai is zero and bi is zero - just turn ai to one (since it will be smaller then B); ai is one and bi is also one - just turn bi to zero (it will also be smaller then B); as a result, we can always set all the suffix to 1-bit and then our job now is to find the suffix and then turn all the suffix bits to 1-bit.
1
2
3
4
5
6
7
8
9
int maxXor(int l, int r) {
int maxVal = 1, count = 0;
while(l != r){
l >>= 1;
r >>= 1;
maxVal |= 1<<count++;
}
return maxVal;
}

The other more efficient way to turn all the suffix to 1-bit.

1
2
3
4
5
6
7
8
9
int maximal(int l, int r){
int maxVal = l^r;
maxVal |= maxVal>>1;
maxVal |= maxVal>>2;
maxVal |= maxVal>>4;
maxVal |= maxVal>>8;
maxVal |= maxVal>>16;
return maxVal;
}

Always welcome new ideas and practical tricks, just leave them in the comments!