Best way to do powerOf(int x, int n)?

So given x, and power, n, solve for X^n. There's the easy way that's O(n)... I can get it down to O(n/2), by doing

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

Now there's a O(log(n))开发者_如何学JAVA solution, does anyone know how to do it? It can be done recursively.

---

Well, you know that x^a+b = x^a x^b so...

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

---

The mathematical concept that can be exploited is that x2n+1 = x2n ⋅ x and x2n = xn ⋅ xn.

---

The usual implementation is something along these lines (cribbed from the wikipedia article):

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

Recursion isn't necessary or (I'd say) particularly desirable, although it can win on obviousness:

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

Of course in any version you overflow a long pretty quickly. You can apply the same algorithms to your favourite bigint representation, although any bigint library is going to include an integer power function already.

Both versions of the function above return 1 for power(0,0). You may or may not consider this a bug.

---

You'll find an explanation here: Fast exponentiation. For some values of n, you can calculate x^n with fewer multiplications than by using the powers of two trick.

---

The standard trick is to generate the powers of x in sequence x², x⁴, x⁸, x¹⁶, x³², ... and include those that are needed in the result.