Maximizing XOR Discussions | Algorithms | HackerRank
  • + 2 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