You are viewing a single comment's thread. Return to all comments →
How did you arrive to the solution? plz explain...
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 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 .
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.