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

###### https://stackoverflow.com/questions/2542507

### OTHER TIPS

The mathematical concept that can be exploited is that `x`

and ^{2n+1} = x^{2n} ⋅ x`x`

.^{2n} = x^{n} ⋅ x^{n}

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^{2}, x^{4}, x^{8}, x^{16}, x^{32}, ... and include those that are needed in the result.