# Maximizing XOR

# Maximizing XOR

RodneyShag + 20 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.

nm1511 + 0 comments pro!

I0000 + 0 comments Nice solution :)

snaran + 0 comments 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; } }

dinthedon + 0 comments thank you

seshu_techie + 3 comments 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;

dsagar + 2 comments How did you arrive to the solution? plz explain...

H__CL + 2 comments 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 .

sanchit2812 + 1 comment [deleted]H__CL + 0 comments 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.

aivi9891 + 0 comments Thxxx!! :)))

facitoo + 0 comments [deleted]

sk_roy + 0 comments explain plz..

170030539SL + 0 comments nice code!!! beautiful logic

AnonymousNovice + 0 comments Thank You @rshaghoulian.

abstractime + 0 comments Great one Â¡Â¡Â¡Â¡!!!!!

h1485237610 + 0 comments [deleted]h1485237610 + 0 comments [deleted]h1485237610 + 0 comments public static void main(String[] args) { try (Scanner sc = new Scanner(System.in);) { int l = sc.nextInt(); int r = sc.nextInt(); System.out.println(allOne(l ^ r)); } } public static int allOne(int i) { i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i; }

theBeacon + 1 comment 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.

RodneyShag + 1 comment 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.

theBeacon + 0 comments Thanks for explaining. A very few explain code well. Keep it up.

alphazygma + 1 comment 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.

RodneyShag + 0 comments 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.

saif01md + 0 comments int n=32-Integer.numberOfLeadingZeros(l^r); System.out.println((int)Math.pow(2,n)-1);

mehmetmustafa + 1 comment Nice solution. It can be written in one line:

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

akhilgautam123 + 0 comments I didn't get this. Somenone plz explain this thing.

nabilpatel1107 + 1 comment @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?

RodneyShag + 1 comment 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.

nabilpatel1107 + 0 comments Thanks.

navi25 + 0 comments 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.

gursoyserhan + 0 comments 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); }

eloyekunle + 1 comment In the spirit of this solution, here's one in Python:

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

m_den + 0 comments Cool! How did you come up with this solution?

alimobasshir21 + 0 comments genius!!

aditya_jha + 0 comments good observation !

R101154 + 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.

kokabi + 2 comments Me Too!

eagle31337 + 1 comment Check range =)

dtudury + 0 comments thank you!

L and R are inclusive (really, that was pretty clear... but for loops write themselves and prefer

`<`

to`<=`

)

uvijay + 0 comments waste of time

abhiranjan + 0 comments @ pr0grammer1, it seems you are able to solve this problem :) Let us know if you have any other query.

s4weng + 0 comments Me too, I don't understand this!

harinani04 + 0 comments guys just check your code once again...it's working for me...check if the "2nd for" loop is considering the last element of array...

tgyurjyan + 0 comments the same(

prasenreddy + 0 comments SMALL

NoNo2 + 2 comments Question should be with strict time limit

siqi_lin + 4 comments I wonder if there's an algorithm to compute it in faster than O(n^2) time.

Goodwine + 3 comments It is possible to make a solution

`O(b)`

where`b`

is the position of the most significant bit of`R`

Hint:

`L=7,R=8`

, and*mostSignificantBit*.benpfisher + 1 comment Is this considered constant time? I think so.

Goodwine + 0 comments No, it is not, it's actually

`O(log2(R))`

, finding the most significant bit is not constant.I was just a bit naive, and didn't see that in my case

`b = f(R) = log2(R)`

mcihanozer + 0 comments Could you give us more content about this solution?

Thanks!

dead_pool + 1 comment sir can you explain how the below solution is solving this problem.

def maxXOR(L,R): P = L^R ret = 1 while(P): # this one takes (m+1) = O(logR) steps ret <<= 1 P >>= 1 return (ret - 1)

i dont understand that how we are getting right answer by doing this method.

conkosidowski + 1 comment Consider this: https://www.hackerrank.com/challenges/maximizing-xor/submissions/code/44305239

- Strip your number down to the most significant bit followed by some amount of 0s or 1s thereafter. This can be done using l^r. The first time one of the numbers has a 1 and the other doesn't, this will be your most significant bit.
- Set all the following 0s to 1s. If 1000 is your most significant, the maximum will be 1111.
- Print the decimal interpretation of the resulting binary number.

dead_pool + 1 comment Thanks buddy for response.But can you explain why we are replacing all zeros to ones after most significant digit.

conkosidowski + 0 comments The best way I can explain it is with examples.

8 is 1000 and 7 is 0111. Anything between 8 and 0 is going to be 15 because your highest XOR number is 1111. As you can see, you can find this by finding the most significant bit and flipping all the following to 1.

8 is 1000 and 9 is 1001. Here you'll find that the answer is 0001. This is because 8 and 9 share the same most significant bit. So after XOR the most significant bit is 0001.

27 is 11011 and 8 is 01000. Here your MSB is 10000 and you can choose 10111 and 01000.

I wish I could explain it better but it's easiest to notice the pattern and go from there. Every answer will always be a power of 2 minus 1, so every answer is always a series of 1s.

furskytl + 1 comment I think it can be O(logR) complexity.

benpfisher + 1 comment It can be better than log(R). If R and L are 4 byte integers, it can be done in 31 steps worst case.

Goodwine + 1 comment No, it's not worse, it's the same.

What you are saying is`log2(R)`

.xshanz + 2 comments in computer science, log(n) means log2(n)

jameseamaya + 1 comment lg(n) means log2(n), log(n) means log10(n). usually

aonurdemir + 0 comments no it is not

mah61 + 0 comments doesn't matter, logs of any base are big-O equivalent

Alphablackwolf + 2 comments I have it in constant O(1) time here:

https://www.hackerrank.com/challenges/maximizing-xor/forum/comments/46432

antitau + 1 comment c++, same complexity, but probably faster on newer processors, although not directly portable:

#include <climits> int maxXor(int a, int b) { if(a^=b) return ~INT_MIN>>__builtin_clz(a)-1; return 0; }

akshay_megharaj + 1 comment How does a compiler compute 'number of leading zeros' in O(1)? I think this solution is O(b) where b is the index of MSB in a^b

antitau + 0 comments The idea in my example is to use the processor instruction that does this in hardware. Of course, it depends on the specific processor brand, type and model how fast the hardware implementation actually is. (or if such instruction exists at all)

akshay_megharaj + 2 comments Although your code is O(1), any O(b) solution will be of the same complexity or perhaps even faster for cases where b < 4. Here b is the index of MSB in a^b.

A very simple O(b) solution that will work for any values of L & R and will work faster than above code for cases where b < 4

int maxXor(int a, int b) { int value = a ^ b, result = 1; while (value) { value = value >> 1; result = result << 1; } return result - 1; }

sushrut619 + 1 comment Nice solution. How does one deduce a solution like this ?

Before peeking into the discussion forum, I was thinking that if l is 0 then the answer would be r ^ 0 = r. Hence, when l is not 0 the answer should have something to do with r ^ l. But I could not take my thought process any further.

akshay_megharaj + 0 comments For me what works is taking a few examples and trying to find a pattern. Once I find a pattern, I convince myself that it will work for all cases or try to find a test case that will fail. Once I find a test case that fails I'll try to modify the pattern or come up with a new pattern. Like in this case the pattern was the MSB that differs between the two numbers. Hope this helps.

gagandeep2598 + 1 comment Can you please explain how you came up with this soultion. Thanks :)

dead_pool + 0 comments editorial

ankitrhode + 0 comments Time complexity is O(n); Ex:1 2 3 4 5 l=1 and r=5 property:Ex-or operations commutative. 1@2 2@4 3@4 4@5 1@3 1@4 1@5 first time,it take n-1 @(ex-or) operation and after that only 1 for each input

jeremy_roy + 0 comments Solution in O(g) time, where g is the MSF of (l xor r). For a 32 bit unsigned integer, worst-case g would be 32 operations.

int maxXor(int l, int r) { int a = l ^ r; int max = 0; while (a != 0) { max |= a; a = a >> 1; } return max; }

ram_bgl09 + 0 comments int _l= Integer.parseInt(in.nextLine()); int _r= Integer.parseInt(in.nextLine()); System.out.println((int)Math.pow(2, Integer.toBinaryString(_l^_r).length())-1);

My solution in java.

Hiba007 + 2 comments Just One Line

return max([i^j for i in range(l, r+1) for j in range(i, r+1)])

vasilij_kolomie1 + 0 comments [deleted]Tej_Pratap_Singh + 0 comments neat.

[deleted] + 0 comments Seems to be a basic problem. A concept of nested loop and fetching of max values. Otherwise took 10 mins to understgand the problem. Good.

sanne09 + 1 comment I'm new to programming so sorry if it's a dumb question but I have to convert the decimal integers into binary right?

jberlage + 4 comments Nope, you won't have to do any explicit conversion. Decimal integers are represented as binary under the hood. You'll want to look into the bitwise operators, they can be used on integers and are a useful way to manipulate the underlying bits.

sanne09 + 0 comments [deleted]sanne09 + 1 comment I didn't know that. Thanks jberlage.

user983783 + 0 comments I was actually struggling with this problem because I thought that I had to convert from decimal to binary. I didnt know I could simply use var03=var01^var02; he he...

teamdebo + 2 comments There is no such thing as decimal integers. Decimal values are NOT integers, they are called floating point values and are stored in memory through approximation unlike integers which are exact values.

This is very important to understand and remember because this is exactly the reason why you never ever ever use decimal/floating point variables to store or calculate values of high precision such as currency because the approximations which are floating point values can result in arithmetic error when many calculations are performed.

The reason I'm leaving this comment is not to be arrogant but to make a point that there is a fundamental difference in the way integers are stored in memory and if you want to save yourself hours of wasted time looking for devious bugs, read up about these differences.

Omnikron13 + 0 comments Actually, the 'integers' passed in from stdin aren't binary integers or decimal integers. They're a string of ASCII characters, which -do- need to be converted.

Depending on language, you very well might need to do explicit conversion to get actual integers.

Remember, the dude said he was new to programming, you need to be careful how you answer such questions. =P

sajid_cse + 0 comments there is an efficient solution for this...

# include

using namespace std; int main() { int m,n; cin>>m>>n; int x=m^n; int k=log2(x)+1; cout<

}

ansua57 + 0 comments #include <bits/stdc++.h> using namespace std; int main() { int a,b; cin>>a>>b; int A=0,c; int i=a; while(i<=b) { int j=a++; while(j<=b) { c=i^j; A=max(A,c); j++; } i++; } cout<<A; }

Sort 262 Discussions, By:

Please Login in order to post a comment