power()函数只适用于整数

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

复杂度= O(exp)

Power()函数为负exp和浮点基数工作。

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

复杂度= O(exp)

如果要取2的a次方。最快的方法是按幂位移位。

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

下面是Java中的方法

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp & 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

迟到的人:

下面是一个尽可能处理y < 0的解。

It uses a result of intmax_t for maximum range. There is no provision for answers that do not fit in intmax_t. powjii(0, 0) --> 1 which is a common result for this case. pow(0,negative), another undefined result, returns INTMAX_MAX intmax_t powjii(int x, int y) { if (y < 0) { switch (x) { case 0: return INTMAX_MAX; case 1: return 1; case -1: return y % 2 ? -1 : 1; } return 0; } intmax_t z = 1; intmax_t base = x; for (;;) { if (y % 2) { z *= base; } y /= 2; if (y == 0) { break; } base *= base; } return z; }

这段代码使用了一个永久循环for(;;)，以避免在其他循环解决方案中常见的最终基数*=基数。这个乘法是1)不需要的，2)可能是int*int溢出，也就是UB。

请注意，平方求幂并不是最优的方法。这可能是一种适用于所有指数值的通用方法，但对于特定的指数值，可能有更好的序列，需要更少的乘法。

例如，如果你想计算x^15，用平方求幂的方法会给你:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

这一共有6次乘法。

事实证明，这可以通过“仅仅”5次加法链幂运算来完成。

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

没有有效的算法来找到这个最优的乘法序列。从维基百科:

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a¹⁵ above, the subproblem for a⁶ must be computed as (a³)² since a³ is re-used (as opposed to, say, a⁶ = a²(a²)², which also requires three multiplies).

更一般的解决方案考虑负指数

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}