# 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;
}

-

We need to maximise the xor between 'small' and 'high'. So let's take an example to understand this.

5 xor 2 = 101 xor 010 first case: MSB bit is not set for both the values in the range.If want to maximimize this then what we need to do is to keep the MSB of 5 (100) as it is and think about maximizing the remaining lower bits. As we know that lower bits all will be one for the case when everything is 11 which is nothing but 3 i.e. 2^2-1. Since the problem is talking about the range between 2 to 5 we defintely have 3 in the range. So all we need to do is to find out the highest MSB set in the larger of 2 values and add the remaining 1's for the lower bits.

second case: As for the case when MSB is set for both the values in the range doing xor will defintely have those bits set as 0 and we need to go back to lower bits. Again for lower bits we need to repeat the same logic as first case. example: (10, 12) (1010, 1100) As you can see both have MSB set as 1 then we have to go back to lower bits which is 010 and 100. Now this problem is same as the first case.

There are several ways to code this. What I did is to do just the xor between 'small' and 'high' and that will remove MSB bit if both 'small' and 'high' have MSB bit set. Incase that is not the case then it will preserve the MSB bit. After that I am trying to make all lower bits 1's by finding out the maximum power of 2 in the xored output and subtracting from 1.

def range_xor_max(small, high):
if small == high:
return 0
xor = small ^ high
#how many power of 2 is present
how_many_power_of_2 = math.log(xor, 2)
#we need to make all one's below the highest set bit
return 2**int(math.floor(how_many_power_of_2)+1) - 1

-
Please don't format your entire answer as code. It makes it very hard to read, especially because the lines are longer than my screen so I have to scroll. – David Richerby Mar 24 at 20:59
Let me change that – noman pouigt Mar 24 at 21:02

For each binary digit, there are 4 possibilities: 1_and_1, 1_and_0, 0_and_1, or 0_and_0. The possible lower digits makes no or log-vanishingly-small difference to the xor output of choice of the next digit. The best possible algorithm is to ignore all lower digits and only consider the next 2 avaiable, given earlier choices about higher digits. If this is 1_and_1 or 0_and_0, the choice is clear, but if this digit is 1_and_0 vs 0_and_1 (which have equal xor but unequal value) then recursively it should equal the https://en.wikipedia.org/wiki/Edit_distance algorithm, meaning worst case of log squared.

-
I'm not sure what you mean by "lower digit", "log-vanishingly-small" or "it... meaning worst case of log squared." Could you clarify? – David Richerby Mar 24 at 2:15