Maximizing XOR Discussions | Algorithms | HackerRank
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.
  1. Practice
  2. Algorithms
  3. Bit Manipulation
  4. Maximizing XOR
  5. Discussions

Maximizing XOR

  • seshu_techie + 4 comments

    It is a nice solution. My solution is similar with no additional method calls. 

    		int x = l ^ r;
		int max = 0;
		while(x > 0)
		{
			max <<= 1;
			max |= 1;
			x >>= 1;
		}
        return max;

    • dsagar + 2 comments

      How did you arrive to the solution? plz explain...

      • H__CL + 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

        • sanchit2812 + 1 comment
          [deleted]

          • H__CL + 0 comments

            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.

        • aivi9891 + 0 comments

          Thxxx!! :)))

      • facitoo + 0 comments
        [deleted]

    • sk_roy + 0 comments

      explain plz..

    • 170030539SL + 0 comments

      nice code!!! beautiful logic

    • yashjain0333 + 0 comments

      Thanks for the solution, loved it!!