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

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?

-

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|}$.

-
Well, that was easy! I guess I should've given this problem more thought. –  Jacopo Notarstefano Aug 30 '14 at 10:19

It is possible to do it in $\mathcal{O}(\log r)$ time.

The maximum possible XOR of any two integers from an interval $[l, r]$ can be determined from $l \oplus r$, assuming $l, r$ to be integers. This value is equal to $2^p-1$, where $p$ is the smallest value such that $2^p$ is larger than $l \oplus r$.

Here is an implementation in C++

int maximumXOR(int l, int r) {
int q = l ^ r, a = 1;
while(q){
q /= 2;
a <<= 1;
}
return --a;
}

-