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.
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 .
Maximizing XOR
You are viewing a single comment's thread. Return to all 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 .
ipynotebook here