使用位移位求整数平方根的最快方法是什么？

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

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

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

令“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;

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