Maximizing XOR

Question

Given 2 integers l and r, find the maximal value of a xor b, where a and b satisfy the following condition:
l ≤ a ≤ b ≤ r
For example, if l = 11 and r = 12, then

11⊕11 = 0
11⊕12 = 7
12⊕12 = 0

Our maximum value is 7.

Naive Solution

A naive solution is to calculate XOR value for all values in the range and find the maximum.

def maximizingXOR(l, r):
    # Since xor of equal values is 0
    if l == r:
        return 0
    # Set an initial max value
    _max = -1
    # Iterate over all values in the range
    for i in range(l, r+1):
        for j in range(l, r+1):
            # Replace the max value if the xor is greater than the current max value
            _max = max(i ^ j, _max)
    # Return the max value
    return _max

Time Complexity

O(N²) where N is the range i.e. N = r - l + 1.

Efficient Solution

Lets look at the XOR operation first. For binary values, XOR is:

0⊕0 = 0
1⊕1 = 0
0⊕1 = 1
1⊕0 = 0

So, XOR is 0 for same bits and 1 for different bits.

Now, lets consider the pattern of binary values from l to r. Since l is smaller than r, so the first bit from l to r either changes from 0 to 1 or it remains 1.

Example 1:
l = 10 = (01010)₂
r = 20 = (10100)₂
Here the first bit changes from 0 to 1.

Example 2:
l = 10 = (1010)₂
r = 15 = (1111)₂
Here the first bit remains 1.

So if we take XOR of any 2 numbers in the range [l, r], for maximum value their first bit will be fixed which will be the same as the first bit of XOR of l and r itself.

Now lets observe the XOR of l and r. From its most significant bit, we know that the maximum XOR value in the range will have the same most significant bit. Its most significant bit also tells us the maximum value we can achieve i.e. let XOR of l and r be 1xxx where x can be 0 or 1 then maximum XOR value we can get is 1111 because from l to r its possible to choose 2 numbers in such a way that all x in xxx become 1.

Example 1:
l = 10 = (01010)₂
r = 20 = (10100)₂
l ^ r = (01010) ^ (10100) = (11110)
Now as l ^ r is of the form (1xxxx), we get the maximum XOR as (11111) by choosing a and b as 15 and 16 (01111 and 10000).

Example 2:
l = 10 = (1010)₂
r = 15 = (1111)₂
l ^ r = (1010) ^ (1111) = (0101)
Now as l ^ r is of the form (1xx), we get the maximum XOR as (111) by choosing a and b as 10 and 13 (1010 and 1101).

So to get the maximum XOR value, we just need (l ^ r). Calculate (l ^ r) first and then from most significant bit of this value, we will add all 1s to get the final result.

Efficient Solution 1

def maximizingXOR(l, r):
    result = 1
    xor = l ^ r  # 1xxx
    # iterate for (MSB+1) times
    while xor:
        result <<= 1
        xor >>= 1
    # return MSB with all added 1s i.e. if xor was 1xxx return 1111
    return result - 1

Time Complexity

O(logN) where N is the range i.e. N = r - l + 1.

Efficient Solution 2

Another solution is to directly use the log function to get the most significant bit.

import math

def maximizingXOR(l, r):
    # log(0) is not possible, so condition to prevent it
    if l == r:
        return 0
    return (1 << (int(math.log(l ^ r, 2)) + 1)) - 1

Time Complexity

O(1) assuming log function takes O(1) time.