用C语言求一个整数的幂的最有效方法是什么?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
用C语言求一个整数的幂的最有效方法是什么?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
当前回答
如果您在编译时知道指数(并且它是一个整数),您可以使用模板展开循环。这可以更有效,但我想在这里演示基本原则:
#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;
}
其他回答
一种非常特殊的情况是,当你需要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浮点数的知识,其他幂运算的特殊情况可能会出现。
平方求幂。
int ipow(int base, int exp)
{
int result = 1;
for (;;)
{
if (exp & 1)
result *= base;
exp >>= 1;
if (!exp)
break;
base *= base;
}
return result;
}
这是在非对称密码学中对大数进行模求幂的标准方法。
另一个实现(在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;
}
}
int pow( int base, int exponent)
{ // Does not work for negative exponents. (But that would be leaving the range of int)
if (exponent == 0) return 1; // base case;
int temp = pow(base, exponent/2);
if (exponent % 2 == 0)
return temp * temp;
else
return (base * temp * temp);
}
我的情况有点不同,我试图用一种力量创造一个面具,但我想无论如何我都要分享我找到的解决方案。
显然,它只适用于2的幂。
Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;