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 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

• 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 \$m = 2^{b+1}-1\$

In the example:

47 101111
48 110000
47 XOR 48 = 31

StackExchange Code Review Q#79885, answer score: 4