x 的平方根

Posted on Sep 05, 2024 By ᵇᵒ

sqrt(x)

LeetCode 69

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

  • 0 <= x <= \(2^{31} - 1\)

二分查找

int mySqrt(int x) {
    if (x == 0) return 0;
    int l = 1, r = x;

    while (l <= r) {
        int m = l + (r - l) / 2;
        if (m <= x / m) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    return r;
}

牛顿迭代

int mySqrt(int x) {
    long r = (x + 1L) / 2;
    while (r * r > x) r = (r + x / r) / 2;
    return r;
}

0x1fbd1dfb

int mySqrt(int x) {
    long i;
    float y;
    const float half = 0.5F;

    y = x;
    i = * ( long * ) &y;                // evil floating point bit level hacking
    i = 0x1fbd1dfb + ( i >> 1 );        // what the fuck?
    y = * ( float * ) &i;
    y = half * ( y + x / y );           // 1st iteration
    y = half * ( y + x / y );           // 2nd iteration

    int r = ( int ) y;
    if ( r > 0 && r > x / r ) r--;
    return r;
}

如上 C 代码在 LeetCode 运行会报错：

Line 7: Char 9: runtime error: load of address 0x7feda5c00030 with insufficient space for an object of type 'float' [solution.c]
0x7feda5c00030: note: pointer points here
 00 00 00 00  00 00 80 40 00 00 00 00  00 00 00 00 00 00 00 00  00 04 00 00 00 00 00 00  00 00 00 00
              ^

第 7 行将 float 类型的指针（&y）强制转换为 long * 类型的指针，并尝试通过该指针获取 float 的 long representation。
float 在内存中使用 32 位表示，而 long 视平台而定可能为 32 位，也可能为 64 位。
LeetCode 使用了内存检测工具 Address Sanitizer，当 long 为 64 位时可能存在内存对齐问题。
为了消除不同平台位数差异的影响，将 long 类型修改为 32 位整型 int/int32_t：

int mySqrt(int x) {
    long i;
    float y;
    const float half = 0.5F;

    y = x;
    i = * ( int * ) &y;                 // evil floating point bit level hacking
    i = 0x1fbd1dfb + ( i >> 1 );        // what the fuck?
    y = * ( float * ) &i;
    y = half * ( y + x / y );           // 1st iteration
    y = half * ( y + x / y );           // 2nd iteration

    int r = ( int ) y;
    if ( r > 0 && r > x / r ) r--;
    return r;
}

需要注意的是，使用 magic number + 牛顿迭代求出的结果更接近真正的平方根，与题目向下取整的要求有一点差异，所以最后还需要多一步判断是否减 1。