Maximise XOR of two elements

Question

I have a number x and I need to choose another number y from the given range [l, r] such that x XOR y is maximum.

This is what I did till now:

def maxXOR(x, l, r):
    max_ = 0
    for y in range(l, r+1):
        temp = x^y
        if temp>max_:
            max_ = temp
    return max_

But it is quite slow. How can I optimise it?

Answer 1

As to the algorithm

The general rule here is don't search when you can calculate.

XOR is fundamentally a bitwise operation. Think about what the XOR operation is doing, on a bit by bit basis.

First, consider a simpler problem where you have to maximise the result with any number at all. (limited only to the number of bits in your input number) Suppose your input is an 8 bit number, perhaps 01100111. You want the output to be 11111111. (or 255 in decimal) So find the number that XORs with your input to give that: the first bit should be 1, the next 0, and so on until you get 10011000.

Unfortunately, you can't necessarily do that because you're restricted in the numbers you're allowed to use. Even so, to maximise the number, you need to have bits end up hot if possible, starting with the most significant bit. Work out which ranges within the provided region would leave the most significant bit hot, then look at the next bit, and repeat until there is only one candidate remaining. That way you'll have a loop running the number of bits in your number (say, 8) instead of a loop running the number of possible candidates (say, 256).

---

In more general commentary on the code:

• Python preferred style is to words separated by underscores in function names, as in max_xor.
• Although single letter variable names are probably acceptable with such narrow scope, descriptive names are better. E.g. l and r are not obviously lower and upper bounds.
• Although max_ is legal, I would personally avoid being that close to a reserved word.
• Speaking of that particular reserved word, I'd replace that if with running_max = max(running_max, temp)
• If we're being very pythonic, and not changing your algorithm, you could use a generator comprehension expression for the whole thing. It would look like return max(x^y for y in range(l, r+1))