实现基于整数的幂函数的最有效方法 pow（int， int）

一个非常特殊的情况是，当你需要说 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);
}

通过使用替身作为基本类型，您可以获得 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

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

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

作为对平方幂效率的评论的后续。

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

此外，就代码复杂性而言，这比试图找到最优化的乘法序列更简单，就像 Pramod 的建议一样。

编辑：

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

如果您需要将 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;
}

如果你想得到一个整数 2 的值，提高到某物的幂，最好使用 shift 选项：

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

这效率要高得多。

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

考虑负 exponenet 的更通用的解决方案

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

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

迟到：

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

1. 它使用 的结果 for maximum range。没有规定不适合的答案。intmax_tintmax_t
2. powjii(0, 0) --> 1这是这种情况的常见结果。

3. pow(0,negative)，另一个未定义的结果，返回INTMAX_MAX

   intmax_t powjii(int x, int y) {
     if (y < 0) {
       switch (x) {
         case 0:
           return INTMAX_MAX;
         case 1:
           return 1;
         case -1:
           return y % 2 ? -1 : 1;
       }
       return 0;
     }
     intmax_t z = 1;
     intmax_t base = x;
     for (;;) {
       if (y % 2) {
         z *= base;
       }
       y /= 2;
       if (y == 0) {
         break; 
       }
       base *= base;
     }
     return z;
   }
   

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

我已经实现了一种算法，可以记住所有计算能力，然后在需要时使用它们。因此，例如，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);
}

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

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

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

我使用了 ，但任何宽度（有符号或无符号）都可以使用，只需稍作修改。但是，如果需要使用非固定宽度的整数类型，则需要更改（在使用 ）或类似的东西，这应该进行优化，但它更丑陋，而不是 C 常量表达式。此外，由于在完美正方形的情况下浮点精度，将结果转换为不是很好，但由于我不知道任何实现 - 或任何类型的最大值 - 是完美正方形，你可以接受它。int64_tSQRT_INT64_MAX(int)sqrt(INT_MAX)intsqrt()intINT_MAX

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

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

这是一个用于计算的 O（1） 算法，受此注释的启发。它适用于 32 位签名。x ** yint

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

在溢出时，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;
        }
    }
}