凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 69. Sqrt(x)

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


题目

Implement int sqrt(int x).

Compute and return the square root of x.

题意

实现 int sqrt(int x)。

解法 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;
    }
};