Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
1  
Well, that was easy! I guess I should've given this problem more thought. –  Jacopo Notarstefano Aug 30 at 10:19

It is possible to do it in 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;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.