用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的幂，最好使用shift选项:
Pow(2,5)可以替换为1<<5
这样效率更高。
下面是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;
}
如果要取2的a次方。最快的方法是按幂位移位。
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
这是对平方求幂效率的后续讨论。
这种方法的优点是它在log(n)时间内运行。例如，如果你要计算一个巨大的数，比如x^1048575(2^20 - 1)，你只需要循环20次，而不是使用朴素方法的100万+次。
此外，在代码复杂性方面，它比试图找到最优的乘法序列更简单，这是la Pramod的建议。
编辑:
我想我应该在有人指责我可能会溢出之前澄清一下。这种方法假设您有某种巨大的int库。
int pow(int const x, unsigned const e) noexcept
{
return !e ? 1 : 1 == e ? x : (e % 2 ? x : 1) * pow(x * x, e / 2);
//return !e ? 1 : 1 == e ? x : (((x ^ 1) & -(e % 2)) ^ 1) * pow(x * x, e / 2);
}
是的，它是递归的，但是一个好的优化编译器会优化递归。
