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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


I sense that we can do better than quadratic. Is there a better algorithm for this problem?

share|cite|improve this question
up vote 12 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|cite|improve this answer
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;
        q /= 2;
        a <<= 1;
    return --a;
share|cite|improve this answer

Your Answer


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.