6

我正在寻找计算数字（整数）平方根（整数）的最快方法。我在维基百科中遇到了这个解决方案，它找到一个数字的平方根（如果它是一个完美的平方）或它最近的下完美平方的平方根（如果给定的数字不是一个完美的平方：

short isqrt(short num) {
    short res = 0;
    short bit = 1 << 14; // The second-to-top bit is set: 1L<<30 for long
    // "bit" starts at the highest power of four <= the argument.
    while (bit > num)
        bit >>= 2;
    while (bit != 0) {
        if (num >= res + bit) {
            num -= res + bit;
            res = (res >> 1) + bit;
        }
        else
            res >>= 1;
        bit >>= 2;
    }
    return res;
}

我尝试了很多测试运行来跟踪算法，但我似乎不理解里面的部分while(bit!=0)。有人可以向我解释这部分吗？

4

1 回答 1

3

我也追踪了一些小例子，我想我明白了。据我了解，该算法一次建立一个二进制数字的答案，从最高位到最低位。

让“num_init”是函数开头的 num 的值。假设在某个迭代中，我们有 bit = 4^x 并且 num 等于某个值“num_curr”（快速浏览一下，直到 bit 为 0，它始终是 4 的幂）。那么 res 的形式为 y*2^(x+1)，其中 y^2 + num_curr = num_init，并且 y 小于实际答案，但在 2^x 之内。

这个关于 num、res 和 bit 值的不变量将是关键。在代码中完成的方式是

while (bit != 0) {
    ....
}

正在将我们的假想指针从左向右移动，并且在每一步我们都确定该位是 0 还是 1。

转到第一个 if 语句，假设我们想象的“累积”整数等于 y，我们正在查看 2^x 位。然后，如果 num 的原始值至少为 (y + 2^x)^2 = y^2 + y*2^(x+1) + 4^x，则该位为 1。换句话说，如果 num 在该点的值至少为 y*2^(x+1) + 4^x，则该位为 1（因为我们有 num 的值下降 y^2 的不变量） . 很方便，res = y*2^(x+1) 和 bit = 4^x。然后我们得到后面的点

if (num >= res + bit) {
    num -= res + bit;
    res = (res >> 1) + bit;
}
else 
    res >>= 1;

如有必要，它会在我们的虚构位置添加 1 位，然后更新 res 和 num 以保持不变。最后

bit >>= 2;

更新位并一步一步移动所有内容。

于 2012-06-30T00:37:01.250 回答