要求：Implement
int sqrt(int x). Compute and return the square root of x.
解决方法：
1.牛顿法（Newton's method）
化解：计算 x2 = a 的解，令 y = x2 - a，相当于求解 y = 0 的解，f(x) 如图。
第一步：取 x0 = a / 2 , 如果 x0 不是解，在点( x0，y0) 做切线 y - y0 = (x - x0) * y'0 ，与 x 轴的交点为 x1 = x0 - y0 / y'0 = x0 - (x02 - a) / (2x0) = (x0 + a / x0) / 2 。
第二步：如果 x1 不是解，做一个经过 ( x1，y1) 这个点的切线，与x轴的交点为 x2。
…………
结束条件：
a. f( xi ) ≈ 0;
b. xi ≈ xi-1.
代码：
inline double ABS(double x){
return x > 0 ? x : (-1 * x);
}
class Solution {
public:
int sqrt(int x) {
/* 用牛顿迭代法求浮点数的平方根 */
double g0 = 0, g1 = x;
while(ABS(g1-g0) > 0.9)
{
g0 = g1;
g1 = (g0 + (x / g0)) / 2;
}
return floor(g1); // (int)g1
}
};
2. 分治法（Divide and conquer）
a = 0 时，返回 0.
a = 1 时，返回 1.
a > 1 时，返回的数在序列 1 与 a/2 之间，序列有序，所以可以用二分法查找。
代码如下：
class Solution {
public:
int sqrt(int x){
/*********** 二分法 ************/
/*********************************/
if(x == 0) return 0;
if(x == 1) return 1;
unsigned long long begin = 1, end = x >> 1;
while(begin < end)
{
unsigned long long mid = (begin + end) >> 1;
unsigned long long tem = mid * mid;
if(tem == x) return mid;
else if(tem > x) end = mid -1;
else begin = mid + 1;
}
if(begin = end)
{
unsigned long long tem = end * end;
if(tem <= x) return end;
if(tem > x) return end - 1;
}
else return end;
}
};
3. 构造数字
从高位到低位，依次试探添加 1。
class Solution {
public:
int sqrt(int x) {
int ans = 0;
int bit = 0X40000000;
while(bit > 0) {
ans |= bit;
if (ans > x / ans) {
ans ^= bit;
}
bit >>= 1;
}
return ans;
}
};