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&lt;=r; left++) {
        for(int right=l;right&lt;=r; right++) {
            if((left ^ right) &gt; 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 &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