Optimizing code to find maximum XOR in Java
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 &amp; 1) != (r &amp; 1)) {
            exp = c;
        }
        l &gt;&gt;= 1;
        r &gt;&gt;= 1;
    }
    return (1 &lt;&lt; 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&lt;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 &lt; 2^{b+1}\$

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

In the example:

47 101111
48 110000
47 XOR 48 = 31