Sqrt(x)

Implement integer square root function. There are two ways to solve this problem. The simplier one is using binary search.

public class Sqrt {
public int mySqrt(int x) {
if (x <= 0) return 0;
if (x <= 3) return 1;

long a = 1;
long b = x >> 1;
long mid;

while (a <= b) {
mid = a + ((b - a) >> 1);
if (mid * mid > x) {
b = mid - 1;
} else if (mid * mid < x) {
a = mid + 1;
} else {
return (int)mid;
}
}

return (int)b;
}
}


A more advanced way is Newton's method. To apply Newton's method we have to take notice of:

1. Newton's method is possible to converge to a negative root. On LeetCode, a positive root is required.
2. Intermediate result may exceed int's range
3. We take a max difference of 1 as end condition. Require may lead to infinite looping.
public class Sqrt {
public int mySqrt(int x) {
if (x <= 0) return 0;
if (x <= 3) return 1;

long x0, x1 = x << 1;

do {
x0 = x1;
x1 = (x0 * x0 + x) / (2 * x0);
} while (Math.abs(x0 - x1) > 1);

if (x1 * x1 > x) return (int)Math.abs(x1) - 1;
else return (int)Math.abs(x1);
}
}


Yet another way is to use bit manipulation. We start from the highest bit position and gradually test if a bit can be 1 to the lowest bit position. As for a 32bit number, the highest 1 in binary of its square root is at most at the 16 bit position, so we start from there.

public class Sqrt {
public int mySqrt(int x) {
if (x <= 0) return 0;

long X = x;
long res = 0;
long marker = (1 << 16);

while (marker > 0) {
long tempr = res | marker;
while (tempr * tempr > X) {
marker >>= 1;
tempr = res | marker;
}
res |= marker;
marker >>= 1;
}

return (int)res;
}
}