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.
Well, we are trying to get the maximum bitwise xor between the range of two values. So the first thing to do is determine the first place at which the maximum value and the minimum value differ. Then, we need to get the next upward power of 2 minus one. As others have done, this is taking the xor value of the minimum and the maximum, and subsequently calculating the next highest power of 2, then to minus one is our answer.
Instead of that approach, what I am doing is to first get that xor value, and anything after that first 1 bit should be filled with 1 bits.
So, for example:
l = 3
r = 10
bitwise, those are:
l = 00000011
r = 00001010
the xor value would be 9, or 00001001.
Now, since we can adjust every bit into varying combinations after the first 1 in that sequence, we know that the max xor of (3,10) is going to be 15 (00001111).
What I am doing with the val statements can be split out as such:
val = val | val >> 1, etc.
to substitute our values:
val = 1001 | 0100 (bit shifted to the right one)
with a bitwise or operation done on 1001 and 0100 we get 1101; so now:
val = 1101 | 0011 (bit shifted to the right two)
we now get 1111 as our result. Additional operations make no changes, because it would all be 1111 | 0000. But because this could be a larger value, we would repeat the action for 4, 8, and if r could be any int32: 16.
This leads us to our final returned value of 15. This is a difficult thing to explain, and I feel I haven't done an amazing job with my explanation; but hopefully it helps. Feel free to ask if you need additional clarification.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Maximizing XOR
You are viewing a single comment's thread. Return to all comments →
Well, we are trying to get the maximum bitwise xor between the range of two values. So the first thing to do is determine the first place at which the maximum value and the minimum value differ. Then, we need to get the next upward power of 2 minus one. As others have done, this is taking the xor value of the minimum and the maximum, and subsequently calculating the next highest power of 2, then to minus one is our answer.
Instead of that approach, what I am doing is to first get that xor value, and anything after that first 1 bit should be filled with 1 bits.
So, for example:
l = 3 r = 10
bitwise, those are: l = 00000011 r = 00001010
the xor value would be 9, or 00001001.
Now, since we can adjust every bit into varying combinations after the first 1 in that sequence, we know that the max xor of (3,10) is going to be 15 (00001111).
What I am doing with the val statements can be split out as such:
val = val | val >> 1, etc.
to substitute our values:
val = 1001 | 0100 (bit shifted to the right one) with a bitwise or operation done on 1001 and 0100 we get 1101; so now: val = 1101 | 0011 (bit shifted to the right two) we now get 1111 as our result. Additional operations make no changes, because it would all be 1111 | 0000. But because this could be a larger value, we would repeat the action for 4, 8, and if r could be any int32: 16.
This leads us to our final returned value of 15. This is a difficult thing to explain, and I feel I haven't done an amazing job with my explanation; but hopefully it helps. Feel free to ask if you need additional clarification.