# Maximizing XOR

# Maximizing XOR

+ 31 comments ### Java solution - more efficient than Editorial solution

import java.util.Scanner; public class Solution { public static void main(String [] args) { Scanner scan = new Scanner(System.in); int L = scan.nextInt(); int R = scan.nextInt(); scan.close(); int xored = L ^ R; int significantBit = 31 - Integer.numberOfLeadingZeros(xored); int result = (1 << (significantBit + 1)) - 1; System.out.println(result); } }

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

L = 10111 R = 11100 _X___ <-- that's most significant differing bit 01111 <-- here's our final answer

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

From my HackerRank solutions.

+ 2 comments I just want to say, I wrote about 75 lines of code because I did not know about the integer bitwise operator ^. I did learn alot though doing everything from scratch :D ...

+ 2 comments Question should be with strict time limit

+ 3 comments **So I spent almost 2 hours to figure out this and this will definitely help you to save your time and clear your confusion.**Let's suppose we take

`l = 83`

and`r = 89`

.83 = 1010011

89 = 1011001

Now we can divide binary strings of l and r into two parts based on the most significant different bit.

positions ->6,5,4 3,2,1,0 83 = 101 0011 89 = 101 1001

Now position 3 is the leftmost position where the bits are different, anything to the left will not change because if we do so then it will either be less than l or becomes greater than r based upon the changes we make, since it is our constraint to remain inside the range

.`l <= a,b <= r`

**So the only changes we can make is in the second part of the binary strings.****Now watch this:****This is all possible permutations of a 4 bits long binary string.**0000----------------| 0001--------------| | 0010------------| | | 0011----------| | | |----------| 0100--------| | | | | | 0101------| | | | | | | 0110----| | | | | | | | 0111--| | | | | | | | | 1000--| | | | | | | | | 1001----| | | | | | |----------| 1010------| | | | | | 1011--------| | | | | 1100----------| | | | 1101------------| | | 1110--------------| | 1111----------------|

In this pattern you can easily see that every line connects two different binary strings and they can be pairs

**a**and**b**, smaller one being**a**and larger one being**b**.So that

`a^b = 1111`

**Since our range is between 0011 to 1001 (from our original example of l = 83 and r = 89)**We can see that pairs

`0111 ^ 1000`

result in`1111`

So we can say that if we make sure that,

**most**significant bit of any two given binary strings are different i.e one is 0 and another one is 1 then we will always get atleast one pair between those range whose`xor(^)`

will result in that bit long string with all the bits set to 1.**Conclusion**you only need to find the position of leftmost different bit for`l`

and`r`

and after that it is not wrong to say that the maximum value of xor of any two numbers between that range will be equal to**111...(n+1) times**where**n**is the position of the*leftmost different bit.*In our case it is

`1111 = 15`

.

+ 7 comments I'm getting a wrong answer on test case 1. I looked at the test case and when I copy and paste the test case in myself -- it works just fine. All other test cases run just fine without any errors.

I believe there is something wrong with the test.

Sort 387 Discussions, By:

Please Login in order to post a comment