以下是计算整数平方根的简单方法:
int isqrt(int num)
{
int root=0;
int b = 0x8000;
int a=0, c=0;
while (b) {
c = a|b;
if (c*c <= num)
a |= b;
b >>= 1;
}
}
巧妙地(感谢Wikipedia),可以这样优化:
int sqrt(short num)
{
int op = num;
int res = 0;
int one = 1 << 30;
while (one > op)
one >>= 2;
while (one != 0) {
if (op >= res + one) {
op -= res + one;
res = (res >> 1) + one;
}
else
res >>= 1;
one >>= 2;
}
return res;
}
我的问题是:是否可以为整数立方根编写类似的优化算法?(这将在一个小型微控制器上运行,该微控制器不进行乘法运算)
最佳答案
根据this的问题和标记的答案,从Hacker's Delight Book可以找到这个实现:
int icbrt2(unsigned x) {
int s;
unsigned y, b, y2;
y2 = 0;
y = 0;
for (s = 30; s >= 0; s = s - 3) {
y2 = 4*y2;
y = 2*y;
b = (3*(y2 + y) + 1) << s;
if (x >= b) {
x = x - b;
y2 = y2 + 2*y + 1;
y = y + 1;
}
}
return y;
}