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