凌云的博客

LeetCode 算法题 69. x 的平方根

分类：algorithm| 发布时间：2017-04-05 14:35:00

---

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解法 1

class Solution {
public:
    int mySqrt(int x) {
        long i = x / 2;
        while (true) {
            long p = i * i;
            if (p == x) return i;
            else if (p > x) i /= 2;
            else if ((i + 1) * (i + 1) > x) {
                return i;
            } else {
                ++i;
            };
        }

        return 0;
    }
};

解法 2

此方法根据 Fast inverse square root 得出

class Solution {
public:
    int mySqrt(int x) {
        uint64_t i;
        double x2, y;
        x2 = x * 0.5;
        y = x;
        i = *(uint64_t *) &y;
        i = 0x5fe6eb50c7b537a9 - (i >> 1); // This magic number is taken from wikipedia.
        y = *(double *) &i; // initial guess of the inverse square root
        y = y * (1.5 - (x2 * y * y)); // Newton for inverse square root.
        y = y * (1.5 - (x2 * y * y));
        y = y * (1.5 - (x2 * y * y));
        y = y * (1.5 - (x2 * y * y)); // repeate 4 times to get enough precision.
        return x * y;
    }
};