Finding the max XOR of two numbers in an interval: can we do better than quadratic?
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&gt;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|}$.