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 nave 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  maxendI sense that we can do better than quadratic. Is there a better algorithm for this problem?
Finding the max XOR of two numbers in an interval: can we do better than quadratic?
algorithms
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|}$.