Optimizing code to find maximum XOR in Java

Question

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?

Answer 1

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