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
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.
Thxxx!! :)))