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

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

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

当前回答

如果你想得到一个整数的2的幂,最好使用shift选项:

Pow(2,5)可以替换为1<<5

这样效率更高。

其他回答

如果你想得到一个整数的2的幂,最好使用shift选项:

Pow(2,5)可以替换为1<<5

这样效率更高。

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

#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的a次方。最快的方法是按幂位移位。

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

我已经实现了记忆所有计算权力的算法,然后在需要时使用它们。比如x^13等于(x^2)^2^2 * x^2 * x其中x^2^2是从表中取出来的而不是再计算一次。这基本上是@Pramod answer的实现(但在c#中)。 需要的乘法数是Ceil(Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}