Finding the max XOR of two numbers in an interval: can we do better than quadratic?

Question Detail: 

Suppose we're given two numbers $l$ and $r$ and that we want to find $\max{(i\oplus j)}$ for $l\le i,\,j\le r$.

The naïve algorithm simply checks all possible pairs; for instance in ruby we'd have:

def max_xor(l, r)   max = 0    (l..r).each do |i|     (i..r).each do |j|       if (i ^ j > max)         max = i ^ j       end     end   end    max end 

I sense that we can do better than quadratic. Is there a better algorithm for this problem?

Asked By : Jacopo Notarstefano

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29508

Answered By : FrankW

We can achieve linear runtime in the length $n$ of the binary representation of $l$ and $r$:

The prefix $p$ in the binary representation of $l$ and $r$, that is the same for both values, is also the same for all values between them. So these bits will always be $0$.

Since $r>l$, the bit following this prefix will be $1$ in $r$ and $0$ in $l$. Furthermore, the numbers $p10^{n-|p|-1}$ and $p01^{n-|p|-1}$ are both in the interval.

So the max we are looking for is $0^{|p|}1^{n-|p|}$.