Question Detail: Suppose we’re given two numbers $l$ and $r$ and that we want to find $max{(ioplus j)}$ for $lle i,,jle 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|}$.
