用C语言求一个整数的幂的最有效方法是什么?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
当前回答
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的幂，最好使用shift选项:
Pow(2,5)可以替换为1<<5
这样效率更高。
另一个实现(在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的幂。
Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
如果要取2的a次方。最快的方法是按幂位移位。
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
如果您在编译时知道指数(并且它是一个整数)，您可以使用模板展开循环。这可以更有效，但我想在这里演示基本原则:
#include <iostream>
template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
return base * exp_unroll<N-1>(base);
}
我们使用模板特化来终止递归:
template<>
unsigned long inline exp_unroll<1>(unsigned base) {
return base;
}
指数需要在运行时已知，
int main(int argc, char * argv[]) {
std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}
