# 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?

• You should let j run through i+1..r and i run through l...r-1 to be precise. – Ahmet Alp Balkan Sep 19 '16 at 20:01

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
• Thread starter asked for "better than quadratic in the numbers". This is linear in the size of the numbers, so it is logarithmic in the numbers themselves. – gnasher729 Sep 20 '16 at 12:10

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


Well, you can use the XOR of l and r to find the answer.

Suppose, l=4 and r = 6.

l = 100, r = 110 (binary equivalents of these numbers)

l⊕r = 010

What this means is, the maximum value you are looking for will definitely have its first bit(MSB) as zero. (Think about it, is it even possible for your maximum value to have a 1 in the first bit instead? If it was 01010 and 00101, the xor would have been = 01111 i.e. the max. value between 01010 and 00101 will definitely have a 1 in their second bit from left, it is not possible to get a 1 before the second bit from left i.e. in the first bit from the left)

So, you are left with the remaining 2 bits to find the maximum. We know, that the maximum possible value when we have n bits with us is = 2n−1, therefore the answer in this case will be 22 -1 = 4-1 = 3.

From the example above, we can make a general algorithm for this.

Step 1. num = number of bits required to represent max(l , r)

Step 2. res = lr

Step 3. pos = Position of the first-bit that is set from the left in res (0-based indexing)

Step 4. n = num - pos

Step 5. ans = 2n−1

Time complexity = O(n)

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 '16 at 2:15

For 32-bit intervals, I just came across this O(1) solution on Hacker Rank editorials. I have no idea how it works, but it works. (Perhaps someone can explain why it works.)

def max_xor(L,R):
v = L^R
v |= v >> 1
v |= v >> 2
v |= v >> 4
v |= v >> 8
v |= v >> 16
return b

• How your answer (after correction) differs from ysb.4's (besides he explained what is going on)? What does 'return b' do with indeclared 'b'? And sorry, but I cannot access the link you have provided. – Evil Sep 19 '16 at 20:25