Hackerrank Solution: Maximizing XOR

Original Problem

Given two integers, \(L\) and \(R\), find the maximal value of \(A\oplus B\), where \(A\) and \(B\) satisfy the following condition:

\(L\leq A\leq B \leq R\)

Input Format

The input contains two lines; \(L\) is present in the first line and \(R\) in the second line.

Constraints
\(1\leq L\leq R\leq 10^3\)

Output Format

The maximal value as mentioned in the problem statement.

Sample Input

10
15

Sample Output

7

Explanation

The input tells us that \(L=10\) and \(R=15\). All the pairs which comply to above condition are the following:
\(10\oplus 10= 0\)
\(10\oplus 11= 1\)
\(10\oplus 12= 6\)
\(10\oplus 13= 7\)
\(10\oplus 14= 4\)
\(10\oplus 15= 5\)
\(11\oplus 11= 0\)
\(11\oplus 12= 7\)
\(11\oplus 13= 6\)
\(11\oplus 14= 5\)
\(11\oplus 15= 4\)
\(12\oplus 12= 0\)
\(12\oplus 13= 1\)
\(12\oplus 14= 2\)
\(12\oplus 15= 3\)
\(13\oplus 13= 0\)
\(13\oplus 14= 3\)
\(13\oplus 15= 2\)
\(14\oplus 14= 0\)
\(14\oplus 15= 1\)
\(15\oplus 15= 0\)

Here two pairs (10, 13) and (11, 12) have maximum xor value 7, and this is the answer.

Solution

This problem can be solved quite trivial by implementing the solution the way it is stated in the description.

def maxXor(l, r)
  m = 0
  for a in l..r
    for b in a..r
      m = (a ^ b) if (a ^ b) > m
    end
  end
  return m
end

However, that's not optimal, since the solution is bound to \(O(lr)\). They say the maximum for the example is (10, 13) and (11, 12), so let's dig into these numbers:

10: 001010
13: 001101
^^: 000111

11: 001011
12: 001100
^^: 000111

XOR is always true if the bits are different. When we look into the original numbers \(l\) and \(r\), we see that

10: 001010
15: 001111

If we would XOR these two numbers, the result would be

^^: 000101

It's not the maximum value we're looking for, but the most significant bit (MSB) is already correct, which means we need to flood the rest with 1 in order to maximize the value in the interval. This means that the maximum depends exclusively on the highest bit set. The MSB is equal to the integer log base 2. In order to maximize the value, we shift the MSB one to the left and subtract 1:

\[f(l, r) = 2 \lfloor\log_2(l\oplus r)\rfloor - 1 \]

The only remaining question is, how can we find an efficient implementation for that. We can loop through the bits, which is bound to \(O(r)\), since \(l\leq r\):

def maxXor(l, r)
  s = l ^ r
  p = 1
  while s > 0 do
    p<<= 1
    s>>= 1
  end
  return p - 1
end

Another idea is to use ruby to make a string representation of the XOR-value and use the length of that as MSB:

def maxXor(l, r)
  return (1 << (l ^ r).to_s(2).size) - 1
end