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.

You are correct, nice catch. That was actually part of prior leftover code I didn't realize wasn't necessary anymore (and actually would mess up some odd cases like l=1, r = 513). Also, since the problem we are given is limits the size of r to <= 1000, we can remove the last bitshift /bitwise or operation and still get valid results for this problem.

(Edit: Code was here, now updated in original comment)

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.

Excellent explanation. One question. You say "Now, since we can adjust every bit into varying combinations after the first 1 in that sequence"... How do we know this?

Ah, so let me start with an example. Lets say L is 92 and R is 95.

L = 1011100

R = 1011111

L xor R would be 0000011. We can create every possible combination WITHIN that 11 because that is the difference between them.

Think of it like a decimal number, if we had numbers of 9480 and 9489 and we were looking for the digits between them we know they all start with '948,' so the only variance is that last digit, which can be 1-9. Take another case, 976590 and 978590. Even though they match a lot, 97_590, that '590' match doesn't matter, only the first difference. we know that the following digits can vary between '6590' all the way through '8590,' giving us a range of 2000 digits.

Similarly, we know that these two binary numbers start with the same digits, and within the range we have we can alter everything after the first mismatch in digits.

I'm thinking that the reason we can be assured there's a combination of bits after the first 1 in the xor result is not because "we can create every possible combination within", but for some other reason.

Between 127 and 128 there are only two possible combinations: 128 xor 127, 128 xor 128. Two combinations doesn't assure us that out of a 6 or 7 digit binary value we will hit every bit pattern. The actual two combinations happen to be 1111111 and 0000000, one of which is all bits set, which is what we need to be assured. But I think it's for some other property of the two binary numbers than the distance between them equals the number of possibilities.

I guess it's just because a binary number xor'd with {itself minus one} is always all bits on?

Ah, fair point for it not really being every possible combination of bits. It's more that you can adjust every bit after that first 1 to not match and thus produce an xor value of 1 for that bit.

Or, more clearly:After that first 1 we can manipulate every non-1 digit by adjusting the values on either side of the xor.

To note, any binary number xor'd with {itself minus one} is not always all bits on, that would only work for a value that is a power of 2.

Thanks for the correction, a binary number xor'd with {itself - 1} is only sometimes all bits on (when a power of 2). I should have looked at more cases before generalizing.

In testing it seems true that every bit of the xor product after the first bit can be arranged to be 1 (when the operands are constrained per this problem, L≤A≤B≤R). I still can't come up with an explanation for why this is the case.

The bigger the span between L and R, the more possibilities there are for finding pairs that xor to 1, but it's not the sheer range of possibilities that makes the magic -- even a span of 1 always assures you the right combinations so that every xor product bit (after the first 1 in the product) is 1. Part of the magic is where the first bit is 1.

Maybe I should ask "What is the significance of the first bit set to 1 in an xor product?" Or, indeed, even what the significance of xor itself is. The answer isn't coming to me. I would not have been able to come up with this algorithm myself.

In any case, I do appreciate your engaging in discussion thus far and sharing your insights. Thanks.

## Maximizing XOR

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

You can use bit shifting and bitwise or checks to get your answer a lot quicker, you avoid doing any loops whatsoever.

(Edit: updated to reflect changes from godoh's comment)

why do you need the decrement? I think it will work fine without it

You are correct, nice catch. That was actually part of prior leftover code I didn't realize wasn't necessary anymore (and actually would mess up some odd cases like l=1, r = 513). Also, since the problem we are given is limits the size of r to <= 1000, we can remove the last bitshift /bitwise or operation and still get valid results for this problem.

(Edit: Code was here, now updated in original comment)

could you please explain your logic

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.

FWIW, this was an excelent explanation to me.

This was awesome ! Thanks

Excellent explanation. One question. You say "Now, since we can adjust every bit into varying combinations after the first 1 in that sequence"... How do we know this?

Ah, so let me start with an example. Lets say L is 92 and R is 95.

L = 1011100

R = 1011111

L xor R would be 0000011. We can create every possible combination WITHIN that 11 because that is the difference between them.

Think of it like a decimal number, if we had numbers of 9480 and 9489 and we were looking for the digits between them we know they all start with '948,' so the only variance is that last digit, which can be 1-9. Take another case, 976590 and 978590. Even though they match a lot, 97_590, that '590' match doesn't matter, only the first difference. we know that the following digits can vary between '6590' all the way through '8590,' giving us a range of 2000 digits.

Similarly, we know that these two binary numbers start with the same digits, and within the range we have we can alter everything after the first mismatch in digits.

Hope that helps!

Something keeps confusing me.

I'm thinking that the reason we can be assured there's a combination of bits after the first 1 in the xor result is not because "we can create every possible combination within", but for some other reason.

Between 127 and 128 there are only two possible combinations: 128 xor 127, 128 xor 128. Two combinations doesn't assure us that out of a 6 or 7 digit binary value we will hit every bit pattern. The actual two combinations happen to be 1111111 and 0000000, one of which is all bits set, which is what we need to be assured. But I think it's for some other property of the two binary numbers than the distance between them equals the number of possibilities.

I guess it's just because a binary number xor'd with {itself minus one} is always all bits on?

Ah, fair point for it not really being every possible combination of bits. It's more that you can adjust every bit after that first 1 to not match and thus produce an xor value of 1 for that bit.

Or, more clearly:After that first 1 we can manipulate every non-1 digit by adjusting the values on either side of the xor.

To note, any binary number xor'd with {itself minus one} is not always all bits on, that would only work for a value that is a power of 2.

Thanks for the correction, a binary number xor'd with {itself - 1} is only sometimes all bits on (when a power of 2). I should have looked at more cases before generalizing.

In testing it seems true that every bit of the xor product after the first bit can be arranged to be 1 (when the operands are constrained per this problem, L≤A≤B≤R). I still can't come up with an explanation for why this is the case.

The bigger the span between L and R, the more possibilities there are for finding pairs that xor to 1, but it's not the sheer range of possibilities that makes the magic -- even a span of 1 always assures you the right combinations so that every xor product bit (after the first 1 in the product) is 1. Part of the magic is where the first bit is 1.

Maybe I should ask "What is the significance of the first bit set to 1 in an xor product?" Or, indeed, even what the significance of xor itself is. The answer isn't coming to me. I would not have been able to come up with this algorithm myself.

In any case, I do appreciate your engaging in discussion thus far and sharing your insights. Thanks.

You explianed it very well. I understood it now. Thanks a lot dude :)

Bloody Awesome... !! Thanx...