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