用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
当前回答
另一个实现(在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;
}
}
其他回答
如果您在编译时知道指数(并且它是一个整数),您可以使用模板展开循环。这可以更有效,但我想在这里演示基本原则:
#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;
}
下面是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的幂,最好使用shift选项:
Pow(2,5)可以替换为1<<5
这样效率更高。
除了Elias的答案,当使用有符号整数实现时,会导致未定义行为,当使用无符号整数实现时,会导致高输入的不正确值,
下面是平方求幂的修改版本,它也适用于有符号整数类型,并且不会给出错误的值:
#include <stdint.h>
#define SQRT_INT64_MAX (INT64_C(0xB504F333))
int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
int_fast64_t base_;
int_fast64_t result;
base_ = base;
if (base_ == 1)
return 1;
if (!exp)
return 1;
if (!base_)
return 0;
result = 1;
if (exp & 1)
result *= base_;
exp >>= 1;
while (exp) {
if (base_ > SQRT_INT64_MAX)
return 0;
base_ *= base_;
if (exp & 1)
result *= base_;
exp >>= 1;
}
return result;
}
使用该函数的注意事项:
(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0
如果将发生任何溢出或换行,则返回0;
I used int64_t, but any width (signed or unsigned) can be used with little modification. However, if you need to use a non-fixed-width integer type, you will need to change SQRT_INT64_MAX by (int)sqrt(INT_MAX) (in the case of using int) or something similar, which should be optimized, but it is uglier, and not a C constant expression. Also casting the result of sqrt() to an int is not very good because of floating point precission in case of a perfect square, but as I don't know of any implementation where INT_MAX -or the maximum of any type- is a perfect square, you can live with that.
我用递归,如果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);
}
}