2ms Java


  • 3

    A typical binary search problem. (l & r) + ((l ^ r) >> 1) avoids the overflow (a much easier alternative is l + (r - l) / 2).

    /* The guess API is defined in the parent class GuessGame.
       @param num, your guess
       @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
          int guess(int num); */
    
    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int l = 0, r = n;
            while (l < r) {
                int m = (l & r) + ((l ^ r) >> 1);
                if (guess(m) == 0) return m;
                else if (guess(m) == 1) l = m + 1;
                else r = m - 1;
            }
            return l;
        }
    }
    

  • 0

    @jianchao.li.fighter said in 2ms Java:

    Why does the divide operation (l & r) + ((l ^ r) >> 1) works?

    I think some folks may have the same question as I first encountered this unfamiliar divide operation. Let me try to add an explanation here:

    • The result of & indicates every bit that has 1 to carry over to higher bit.
    • The result of ^ indicates every bit that has 1 to stay.
    • & * 2 + ^ gives out the addition of two numbers.
    • & + ^ >> 1 gives out the addition of two numbers / 2.
    • &, ^ and >> operations will not overflow even two operands are MAX_VALUE.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.