We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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 ^.

Let , it is easy to see that (since , have at most n bits, so the bitwise xor can not be larger than ).

Now assume that and . This is equivalent to that the binary expansion of and differs by the most significant bit, i.e.,
and .

Then
and satisfies and which achieves the upper bound of the xor of two numbers less than . Thus the maximum of for is , where n is the bit length of .

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.

Hi. I cannot provide a formal mathematical proof, mostly because it would probably take 4 paragraphs of explaining in detail. It's best to just see it always works by going through a few examples on your own.

A good thing to notice is that the number calculated will always be in the actual domain of possible values because my solution says "We first find the most significant bit that we can force to differ by looking at L and R." This is the main step that gets A and B to be in the correct domain.

Your version of the code works also. I used 31 instead of 32 since I count the 32 bits from 0 to 31 instead of 1 to 32. That is, I count the leftmost bit as the 31st bit, and the rightmost bit as the 0th bit.

@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?

Yes, you can do that. I subtract from 31 since I like to number the bits 0 to 31 (from right to left). If you subtract from 32, it's kind of like numbering the bits 1 to 32.

## Maximizing XOR

You are viewing a single comment's thread. Return to all comments →

## Java solution - more efficient than Editorial solution

To maximize A xor B, we want A and B to differ as much as possible at every bit index.

We first find the most significant bit that we can force to differ by looking at L and R.

For all of the lesser significant bits in A and B, we can always ensure that they differ and still have L <= A <= B <= R.

Our final answer will be the number represented by all 1s starting from the most significant bit that differs between A and B

## Let's try an example

Notice how we don't directly calculate the values of A and B.

From my HackerRank solutions.

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 ^.

thank you

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

How did you arrive to the solution? plz explain...

Guess we can prove it like this.

Let , it is easy to see that (since , have at most n bits, so the bitwise xor can not be larger than ).

Now assume that and . This is equivalent to that the binary expansion of and differs by the most significant bit, i.e., and .

Then and satisfies and which achieves the upper bound of the xor of two numbers less than . Thus the maximum of for is , where n is the bit length of .

ipynotebook here

The proof goes like 1. estimate a upper bound of and 2. find and that satisfies the constraint and achieves the upper bound.

Let's say (binary) and , then we can construct:

(put 1 at the most significant bit followed by 0s) and

(put 0 at the most significant bit followed by 1s)

so that . And the constraints are also satisfied.

Hope this example helps.

Thxxx!! :)))

explain plz..

nice code!!! beautiful logic

Thanks for the solution, loved it!!

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.

Hi. I cannot provide a formal mathematical proof, mostly because it would probably take 4 paragraphs of explaining in detail. It's best to just see it always works by going through a few examples on your own.

A good thing to notice is that the number calculated will always be in the actual domain of possible values because my solution says "We first find the most significant bit that we can force to differ by looking at L and R." This is the main step that gets A and B to be in the correct domain.

HackerRank solutions.

Thanks for explaining. A very few explain code well. Keep it up.

I have a question, why did you have

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

Just trying to learn on your reasoning to use 31.

Your version of the code works also. I used 31 instead of 32 since I count the 32 bits from 0 to 31 instead of 1 to 32. That is, I count the leftmost bit as the 31st bit, and the rightmost bit as the 0th bit.

HackerRank solutions.

Nice solution. It can be written in one line:

I didn't get this. Somenone plz explain this thing.

@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?

Yes, you can do that. I subtract from 31 since I like to number the bits 0 to 31 (from right to left). If you subtract from 32, it's kind of like numbering the bits 1 to 32.

HackerRank solutions.

Thanks.

We can also do -

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,

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

Cool! How did you come up with this solution?

genius!!

good observation !

Awe!!!!

Python Oneliner Solution