# 2ms Java

• 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.
@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;
}
}
``````

• @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.

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