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
```