我正在通过位移研究快速平方根算法。我被维基百科的代码困住了。
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;
}
我知道它可以产生正确的结果,但它是如何产生的呢?我对这句话特别困惑,res = (res >> 1) + bit; 为什么 res 应该在这里除以 2?任何人都可以对此有所了解吗?感谢!