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