pro!

Nice solution :)

My way had the same concept as your picture: to calculate the highest order bit that is different and subtract one from it, though my way has a loop that you avoided by doing an ^.

static int maxXor(int l, int r) {
        int lBit = Integer.highestOneBit(l);
        int rBit = Integer.highestOneBit(r);
        if (lBit == rBit) {
            if (lBit == 0) {
                return 0;
            } else {
                int newL = l & (~lBit);
                int newR = r & (~lBit);
                return maxXor(newL, newR);
            }
        } else {
            int max = Math.max(lBit, rBit);
            return (max << 1) -1;
        }
    }

thank you

It is a nice solution. My solution is similar with no additional method calls.

		int x = l ^ r;
		int max = 0;
		while(x > 0)
		{
			max <<= 1;
			max |= 1;
			x >>= 1;
		}
        return max;

Thank You @rshaghoulian.

Great one ¡¡¡¡!!!!!

Whatever number is calculated in this way may not be in actual domain of possible values. How can correctness of this solution can be proved and verified.

I have a question, why did you have

int significantBit = 31 - Integer.numberOfLeadingZeros(xored);

Instead of 32, which represents the 32bits used for an int.

Using the base example of L = 10, R = 15

L ^ R = 1010 ^ 1111 = 0101 = 5

The result of Integer.numberOfLeadingZeros(xored) is 29, which matches 32bits - 3bits (for 5)

And then your result would be

int result = (1 << significantBit) - 1;

Just trying to learn on your reasoning to use 31.

Nice solution. It can be written in one line:

System.out.println(Integer.highestOneBit(L ^ R) * 2 - 1);

@rshaghoulian Instead of substracting from 31 can we substract from 32 and do not add 1 later? or there is something I am missing because of it, it is required to substract from 31?

We can also do -

static int maximizingXor(int l, int r) {
        int xored  = l ^ r;
        int highestBit = Integer.highestOneBit(xored);
        return 2*highestBit -1;   
 }

The logic is same. One additional charactersitics that's been used is:- Sum of all the trailing zeros converted to ones is HighestBit - 1.

For eg - L = 10111
R = 11100 _X___ <-- that's most significant differing bit 01000 <-- This is what HighestBit gave us.

We need to calculate 01111 in int, this can be obtained by sum of 01000 and 00111 and that's equal to 2*highestBit - 1.

This is absolutely great! Here, this is same operation in PHP,

function maximizingXor($l, $r) {
    $xored = $l ^ $r;
    $most = strlen(decbin($xored));
    $bin = '';
    for ( $i =0; $i < $most; $i++) $bin = $bin . "1";
    return bindec($bin);
}

In the spirit of this solution, here's one in Python:

(1 << (len(format(l^r, 'b')))) - 1

genius!!

good observation !

Awe!!!!

Python Oneliner Solution

def maximizingXor(l, r):
    return pow(2,len(bin(l^r))-2)-1