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

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

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

当前回答

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

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

这样效率更高。

其他回答

我的情况有点不同,我试图用一种力量创造一个面具,但我想无论如何我都要分享我找到的解决方案。

显然,它只适用于2的幂。

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

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

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

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

编辑:

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

如果要取2的a次方。最快的方法是按幂位移位。

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

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