Question: The problem asks to find the maximum of a xor b for all pair of integers
pairs of integers a, b (l ≤ a ≤ b ≤ r).If l and R are 8 and 16 ,answer is 31 which is actually 15 xor 16.I came across this piece of code and it gives correct output but the logic part is not clear .

```
int main() {
    cin >> A >> B;
    ll num = 1;
    while (A / num != B / num) {
        num *= 2;
    }
    cout << num - 1 << "\n";
    return 0;
}                                         

```

Answer: 
Well, I can crash that code easily. By entering the same number twice. If l = r then the algorithm crashes, but the largest value for a xor b is obviously 0, since l = a = b = r. 

Assume l < r, and that for some n we have (l / (2^n)) = (r / (2^n)). There is such an n because we can just pick n making 2^n > r. And n > 0 because l < r. Pick the smallest such n. 

In that case, a / (2^n) has the same value for all a, l ≤ a ≤ r. This means that all bits in a^b starting with bit n are zero. Therefore a xor b < 2^n, and we can replace l, r with l modulo (2^n), r modulo (2^n). 

On the other hand, n was chosen as small as possible. Therefore bit n-1 is set in r, while bit n-1 is cleared in l. Therefore l < 2^(n-1), r ≥ 2^(n-1). We can pick a = 2^(n-1) - 1, b = 2^(n-1). Then l ≤ a ≤ b ≤ r, and a xor b = 2^n - 1. Since we showed that a xor b is always less than 2^n, but can be 2^n - 1, it follows that 2^n - 1 is the largest value. 

Exactly what the algorithm calculates, except that l = r isn't handled correctly.
Lets take the example with l = 8 and r = 16, or

```
l = 00010
r = 00001

```

what the code does, is shifting the bits until the numbers are the same:

```
num=2  num=4  num=8  num=16   num=32

00100  01000  10000   00000  00000   
00010  00100  01000   10000  00000   -> done : max xor is 32-1

```

this works, because the biggest xor you can get is the number with as many bits set to 1 as possible, and in general, if you have

```
l = 0001010101010101011111111111110000001010101010...
r = 0010101010101010101101010101010100001010101010...
                                    ^...starting from here they are
                                        the same (no matter what) 

```

the biggest result you can get from an a xor b with l < a < b < r is 

```
    111111111111111111111111111111110000000000000000000...

```