# Optimizing code to find maximum XOR in Java

This problem is from HackerRank (not a competition, just for practice)

Basically what you do is take in two integers as a range and then finding the maximum XOR from a pair of integers in that interval.

Here is my code for doing so (it passed all the test cases):

static int maxXor(int l, int r) {
int maxXor = l ^ r;
for(int left=l;left<=r; left++) {
for(int right=l;right<=r; right++) {
if((left ^ right) > maxXor) {
maxXor = left ^ right;
}
}
}
return maxXor;
}


I was able to tell that this code segment runs in $\mathcal{O}(n^2)$ because the outer for loop will run in $\mathcal{O}(N)$, $N$ as in number of integers in the range, and the inner loop will also run in $\mathcal{O}(N)$. Because each time the outer loop runs, the inner loop runs one time aswell, the entire code segment will in $\mathcal{O}(N^2)$. Is that good analysis?

But anyways, is there an optimization (for performance) for this code segment to get the runtime down to $\mathcal{O}(N)$ or $\mathcal{O}(log N)$ perhaps?

You are correct that your code has $\mathcal{O}(n^2)$ performance.

Here is a solution in $\mathcal{O}(log(n))$:

static int maxXor(int l, int r) {
int c = 0;
int exp = 0;
while (l != 0 || r != 0) {
c++;
if ((l & 1) != (r & 1)) {
exp = c;
}
l >>= 1;
r >>= 1;
}
return (1 << exp) - 1;
}


Explanation

The task of finding the maximum XOR value $m$ is equivalent to finding the most significant bit $b$ that differs between L and R. The maximum XOR value will be $m=2^{b+1}-1$.

Proof sketch

Let's use the number 42 (101010) and 59 (111011) as a running example. The most significant bit that differs is bit 4, therefore we expect $m=31$.

vvvvvv all these bits are equal
00000101010
00000111011
^ bit b=4 differs


Note that bits above $b$ never change when counting from L to R, and since XOR only cares about different bits we have $m<2^{b+1}$ as an upper bound.

But since bit $b$ is set in R and not set in L, there have to be two numbers in the range [L, R] where:

• In the first number x, all bits below $b$ are set.
• In the second number x+1, $b$ is set, but all bits below it are not.

So x XOR x+1 will be equal to the sum of all bits up to and including $b$ which is $2^{b+1}-1$, i.e. $m \geq 2^{b+1}-1$.

Thus we have $2^{b+1}-1 \leq m < 2^{b+1}$

=> $m = 2^{b+1}-1$

In the example:

47 101111
48 110000
47 XOR 48 = 31