用C语言求一个整数的幂的最有效方法是什么?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
当前回答
我用递归，如果exp是偶数，5^10 =25^5。
int pow(float base,float exp){
if (exp==0)return 1;
else if(exp>0&&exp%2==0){
return pow(base*base,exp/2);
}else if (exp>0&&exp%2!=0){
return base*pow(base,exp-1);
}
}
其他回答
我已经实现了记忆所有计算权力的算法，然后在需要时使用它们。比如x^13等于(x^2)^2^2 * x^2 * x其中x^2^2是从表中取出来的而不是再计算一次。这基本上是@Pramod answer的实现(但在c#中)。 需要的乘法数是Ceil(Log n)
public static int Power(int base, int exp)
{
int tab[] = new int[exp + 1];
tab[0] = 1;
tab[1] = base;
return Power(base, exp, tab);
}
public static int Power(int base, int exp, int tab[])
{
if(exp == 0) return 1;
if(exp == 1) return base;
int i = 1;
while(i < exp/2)
{
if(tab[2 * i] <= 0)
tab[2 * i] = tab[i] * tab[i];
i = i << 1;
}
if(exp <= i)
return tab[i];
else return tab[i] * Power(base, exp - i, tab);
}
更一般的解决方案考虑负指数
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);
}
我用递归，如果exp是偶数，5^10 =25^5。
int pow(float base,float exp){
if (exp==0)return 1;
else if(exp>0&&exp%2==0){
return pow(base*base,exp/2);
}else if (exp>0&&exp%2!=0){
return base*pow(base,exp-1);
}
}
另一个实现(在Java中)。可能不是最有效的解决方案，但迭代次数与指数解相同。
public static long pow(long base, long exp){
if(exp ==0){
return 1;
}
if(exp ==1){
return base;
}
if(exp % 2 == 0){
long half = pow(base, exp/2);
return half * half;
}else{
long half = pow(base, (exp -1)/2);
return base * half * half;
}
}
如果你想得到一个整数的2的幂，最好使用shift选项:
Pow(2,5)可以替换为1<<5
这样效率更高。
