将整数提升为C中另一个整数的幂的最有效方法是什么？

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

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

解决方案

忽略2升为幂的特殊情况，最有效的方法将是简单迭代。

int pow(int base, int pow) {
  int res = 1;
  for(int i=pow; i<pow; i++)
    res *= base;

  return res;
}

编辑：正如已经指出的那样，这不是最有效的方法...只要我们将效率定义为cpu周期，我想这是很公平的。

一个非常特殊的情况是，当我们需要说2 ^(-y的-x)时，其中x当然是负数，y太大而无法在int上进行移位。我们仍然可以通过固定浮子在恒定时间内进行2 ^ x的操作。

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};

union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

我们可以通过使用double作为基本类型来获得2的更多次方。
(非常感谢评论者帮助我们平正这篇文章)。

也有可能更多地了解IEEE浮动，其他幂运算的特殊情况可能会出现。

通过平方求幂。

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        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);
}

请注意，通过平方求幂不是最佳方法。作为适用于所有指数值的通用方法，这可能是我们最好的选择，但是对于特定的指数值，可能会有更好的序列，需要较少的乘法。

例如，如果要计算x ^ 15，则通过平方的求幂方法将为我们提供：

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

总共有6个乘法。

事实证明，这可以通过加法链求和使用"仅" 5个乘法来完成。

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

没有找到这种最佳乘法序列的有效算法。从维基百科：

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a1? above, the subproblem for a? must be computed as (a3)2 since a3 is re-used (as opposed to, say, a? = a2(a2)2, which also requires three multiplies).

就像对平方求幂的效率进行评论的跟进一样。

这种方法的优势在于它可以以log(n)的时间运行。例如，如果我们要计算巨大的东西，例如x ^ 1048575(2 ^ 20 1)，则我们只需经过20次循环，而无需使用天真的方法进行100万次以上的循环。

而且，就代码复杂度而言，这比尝试找到最佳的乘法序列要容易得多，这是la Pramod的建议。

编辑：

我想我应该澄清一下，然后再有人标记我溢出的可能性。这种方法假定我们具有某种hugeint库。