algorithm - 按位整数立方根算法

Question

这是计算整数平方根的简单方法:

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;
}

我的问题:是否可以为整数立方根编写类似的优化算法？ (这将在一个不喜欢做乘法的小型微 Controller 上运行)

Answer 1

根据 this所以问题和标记的答案，从 Hacker's Delight 书中你可以找到这个实现:

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;
}