实现基于整数的幂函数 pow(int, int) 的最有效方法

通过平方取幂。

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

这是在非对称密码学中对大量数字进行模幂运算的标准方法。

---

请注意，exponentiation by squaring 不是最佳方法。作为适用于所有指数值的通用方法，这可能是您可以做的最好的事情，但对于特定的指数值，可能会有一个更好的序列，需要更少的乘法。

例如，如果你想计算 x^15，通过平方取幂的方法会给你：

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

这总共是 6 次乘法。

事实证明，这可以通过 addition-chain exponentiation 使用“仅”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

没有有效的算法来找到这个最佳的乘法序列。从 Wikipedia：

寻找最短加法链的问题不能通过动态规划来解决，因为它不满足最优子结构的假设。也就是说，将功率分解为较小的功率是不够的，每个较小的功率计算最少，因为较小功率的加法链可能是相关的（以共享计算）。例如，在上面 a¹⁵ 的最短加法链中，a⁶ 的子问题必须计算为 (a³)²，因为 a³ 被重复使用（与 a⁶ = a²(a²)² 相反，它也需要三个乘法）。

---

如果您需要将 2 提高到一个幂。最快的方法是按功率移位。

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;
}

---

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(log(exp))

power() 函数适用于 负 exp 和 float base。

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(log(exp))

---

一个非常特殊的情况是，当您需要说 2^(-x 到 y) 时，其中 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 floats，其他特殊的求幂情况可能会出现。

---

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);
}

---

如果您想将 2 的整数值提高到某个值的幂，最好使用 shift 选项：

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

这效率更高。

---

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

这种方法的优点是它在 log(n) 时间内运行。例如，如果你要计算一些巨大的东西，例如 x^1048575 (2^20 - 1)，你只需要通过循环 20 次，而不是使用幼稚的方法超过 100 万次。

此外，就代码复杂性而言，它比尝试找到最佳乘法序列更简单，这是 la Pramod 的建议。

编辑：

我想我应该在有人为我标记溢出的可能性之前澄清一下。这种方法假设您有某种 hugeint 库。

---

晚会迟到：

下面是一个解决方案，它也尽可能地处理 y < 0。

它使用 intmax_t 的结果作为最大范围。没有规定不适合 intmax_t 的答案。 powjii(0, 0) --> 1 这是这种情况的常见结果。 pow(0,negative)，另一个未定义的结果，返回 INTMAX_MAX intmax_t powjii(int x, int y) { if (y < 0) { switch (x) { case 0: return INTMAX_MAX;案例1：返回1；案例-1：返回 y % 2 ？ -1：1； } 返回 0; } intmax_t z = 1; intmax_t 基数 = x; for (;;) { if (y % 2) { z *= base; } y /= 2;如果 (y == 0) { 休息; } 基地 *= 基地; } 返回 z; }

此代码使用永久循环 for(;;) 来避免其他循环解决方案中常见的最终 base *= base。该乘法是 1) 不需要和 2) 可能是 int*int 溢出，即 UB。

---

考虑负指数的更通用的解决方案

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

---

Swift 中的 O(log N) 解决方案...

// 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 

}

---

int pow(int const x, unsigned const e) noexcept
{
  return !e ? 1 : 1 == e ? x : (e % 2 ? x : 1) * pow(x * x, e / 2);
  //return !e ? 1 : 1 == e ? x : (((x ^ 1) & -(e % 2)) ^ 1) * pow(x * x, e / 2);
}

是的，它是递归的，但是一个好的优化编译器会优化递归。

---

另一种实现（在 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;
    }       
}

---

我使用递归，如果 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);
   }
}

---

除了 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

如果要发生任何溢出或包装，return 0;

我使用了 int64_t，但只需稍加修改即可使用任何宽度（有符号或无符号）。但是，如果您需要使用非固定宽度的整数类型，则需要将 SQRT_INT64_MAX 更改为 (int)sqrt(INT_MAX)（在使用 int 的情况下）或类似的东西，应该优化，但它是丑陋的，而不是 C 常量表达式。同样将 sqrt() 的结果转换为 int 也不是很好，因为在完美正方形的情况下浮点精度，但我不知道 INT_MAX 的任何实现 - 或任何类型的最大值- 是一个完美的正方形，你可以忍受。

---

我已经实现了记住所有计算能力然后在需要时使用它们的算法。因此，例如 x^13 等于 (x^2)^2^2 * x^2^2 * x 其中 x^2^2 它是从表中获取的，而不是再次计算它。这基本上是@Pramod 答案的实现（但在 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);
}

---

这是一个计算 x ** y 的 O(1) 算法，受 this comment 启发。它适用于 32 位签名 int。

对于 y 的小值，它使用平方取幂。对于较大的 y 值，只有少数 x 值不会溢出。此实现使用查找表来读取结果而不进行计算。

在溢出时，C 标准允许任何行为，包括崩溃。但是，我决定对 LUT 索引进行边界检查，以防止内存访问违规，这可能令人惊讶且不受欢迎。

伪代码：

If `x` is between -2 and 2, use special-case formulas.
Otherwise, if `y` is between 0 and 8, use special-case formulas.
Otherwise:
    Set x = abs(x); remember if x was negative
    If x <= 10 and y <= 19:
        Load precomputed result from a lookup table
    Otherwise:
        Set result to 0 (overflow)
    If x was negative and y is odd, negate the result

C代码：

#define POW9(x) x * x * x * x * x * x * x * x * x
#define POW10(x) POW9(x) * x
#define POW11(x) POW10(x) * x
#define POW12(x) POW11(x) * x
#define POW13(x) POW12(x) * x
#define POW14(x) POW13(x) * x
#define POW15(x) POW14(x) * x
#define POW16(x) POW15(x) * x
#define POW17(x) POW16(x) * x
#define POW18(x) POW17(x) * x
#define POW19(x) POW18(x) * x

int mypow(int x, unsigned y)
{
    static int table[8][11] = {
        {POW9(3), POW10(3), POW11(3), POW12(3), POW13(3), POW14(3), POW15(3), POW16(3), POW17(3), POW18(3), POW19(3)},
        {POW9(4), POW10(4), POW11(4), POW12(4), POW13(4), POW14(4), POW15(4), 0, 0, 0, 0},
        {POW9(5), POW10(5), POW11(5), POW12(5), POW13(5), 0, 0, 0, 0, 0, 0},
        {POW9(6), POW10(6), POW11(6), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(7), POW10(7), POW11(7), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(8), POW10(8), 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(9), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(10), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    int is_neg;
    int r;

    switch (x)
    {
    case 0:
        return y == 0 ? 1 : 0;
    case 1:
        return 1;
    case -1:
        return y % 2 == 0 ? 1 : -1;
    case 2:
        return 1 << y;
    case -2:
        return (y % 2 == 0 ? 1 : -1) << y;
    default:
        switch (y)
        {
        case 0:
            return 1;
        case 1:
            return x;
        case 2:
            return x * x;
        case 3:
            return x * x * x;
        case 4:
            r = x * x;
            return r * r;
        case 5:
            r = x * x;
            return r * r * x;
        case 6:
            r = x * x;
            return r * r * r;
        case 7:
            r = x * x;
            return r * r * r * x;
        case 8:
            r = x * x;
            r = r * r;
            return r * r;
        default:
            is_neg = x < 0;
            if (is_neg)
                x = -x;
            if (x <= 10 && y <= 19)
                r = table[x - 3][y - 9];
            else
                r = 0;
            if (is_neg && y % 2 == 1)
                r = -r;
            return r;
        }
    }
}

---

我的情况有点不同，我正在尝试从力量中创建一个面具，但我想我还是会分享我找到的解决方案。

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

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

---

如果您在编译时知道指数（并且它是一个整数），您可以使用模板来展开循环。这可以提高效率，但我想在这里演示基本原理：

#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;
}

---