做powerOf(int x,int n)的最佳方法是什么？

Question

所以给定x和幂,n,求解X^n.还有这是最简单的方式O(n)...我能得到它归结为O(n/2),通过做

numSquares = n/2;
numOnes = n%2;
return (numSquares * x * x + numOnes * x);

现在有一个O(log(n))解决方案,有谁知道怎么做？它可以递归地完成.

Answer 1

可以利用的数学概念是和.x2n+1 = x2n ⋅ xx2n = xn ⋅ xn

Answer 2

嗯,你知道x ^{a + b} = x ^a x ^b所以......

int pow(int x, unsigned int y)
{
  if (y == 0) return 1;
  if (y == 1) return x;
  int a = y / 2;
  int xa = pow(x, a);
  if (a + a == y) // y even
    return xa * xa;
  else
    return xa * xa * x;
}

Answer 3

通常的实现是这些方面的事情(来自维基百科的文章):

long power(long x, unsigned long n)
{
    long result = 1;
    while (n > 0) {
        /* n is odd, bitwise test */ 
        if (n & 1) {
            result *= x;
        }
        x *= x;
        n /= 2;     /* integer division, rounds down */
    }
    return result;
}

递归是没有必要的或(我会说)特别可取,虽然它可以赢得显而易见性:

long power(long x, unsigned long n)
{
    if (n == 0) return 1;
    long result = power(x, n/2); // x ^ (n/2)
    result *= result;            // x ^ (n/2)*2
    if (n & 1) result *= x;      // x ^ n
    return result;
}

当然,在任何版本中,你很快就会溢出很长时间.您可以将相同的算法应用于您最喜欢的bigint表示,尽管任何bigint库都将包含整数幂函数.

上述函数的两个版本都返回1 power(0,0).您可能会或可能不会认为这是一个错误.