用C语言求一个整数的幂的最有效方法是什么?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

当前回答

这是对平方求幂效率的后续讨论。

这种方法的优点是它在log(n)时间内运行。例如,如果你要计算一个巨大的数,比如x^1048575(2^20 - 1),你只需要循环20次,而不是使用朴素方法的100万+次。

此外,在代码复杂性方面,它比试图找到最优的乘法序列更简单,这是la Pramod的建议。

编辑:

我想我应该在有人指责我可能会溢出之前澄清一下。这种方法假设您有某种巨大的int库。

其他回答

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)

下面是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;
}

O(log N)的解决方案在Swift…

// Time complexity is O(log N)
func power(_ base: Int, _ exp: Int) -> Int { 

    // 1. If the exponent is 1 then return the number (e.g a^1 == a)
    //Time complexity O(1)
    if exp == 1 { 
        return base
    }

    // 2. Calculate the value of the number raised to half of the exponent. This will be used to calculate the final answer by squaring the result (e.g a^2n == (a^n)^2 == a^n * a^n). The idea is that we can do half the amount of work by obtaining a^n and multiplying the result by itself to get a^2n
    //Time complexity O(log N)
    let tempVal = power(base, exp/2) 

    // 3. If the exponent was odd then decompose the result in such a way that it allows you to divide the exponent in two (e.g. a^(2n+1) == a^1 * a^2n == a^1 * a^n * a^n). If the eponent is even then the result must be the base raised to half the exponent squared (e.g. a^2n == a^n * a^n = (a^n)^2).
    //Time complexity O(1)
    return (exp % 2 == 1 ? base : 1) * tempVal * tempVal 

}

如果您在编译时知道指数(并且它是一个整数),您可以使用模板展开循环。这可以更有效,但我想在这里演示基本原则:

#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的幂。

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;