用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
这样效率更高。
如果要取2的a次方。最快的方法是按幂位移位。
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
更一般的解决方案考虑负指数
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);
}
一种非常特殊的情况是，当你需要2^(-x ^ y)时，其中x当然是负的y太大了，不能对int型进行移位。你仍然可以用浮点数在常数时间内完成2^x。
struct IeeeFloat
{
unsigned int base : 23;
unsigned int exponent : 8;
unsigned int signBit : 1;
};
union IeeeFloatUnion
{
IeeeFloat brokenOut;
float f;
};
inline float twoToThe(char exponent)
{
// notice how the range checking is already done on the exponent var
static IeeeFloatUnion u;
u.f = 2.0;
// Change the exponent part of the float
u.brokenOut.exponent += (exponent - 1);
return (u.f);
}
使用double作为基底类型，可以得到更多的2的幂。 (非常感谢评论者帮助整理这篇文章)。
还有一种可能性是，学习更多关于IEEE浮点数的知识，其他幂运算的特殊情况可能会出现。
我的情况有点不同，我试图用一种力量创造一个面具，但我想无论如何我都要分享我找到的解决方案。
显然，它只适用于2的幂。
Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
