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