bit-shift - 使用位移找到整数平方根的最快方法是什么？

Question

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

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) 里面的部分.有人可以向我解释这部分吗？

Answer 1

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

令“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(因为我们有 num 的值下降了 y^2 的不变式)，则该位为 1 .很方便，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;

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