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

Question

在 C 中，将一个整数求另一个整数次方的最有效方法是什么？

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

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

Answer 1

通过平方求幂。

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

    return result;
}

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

Answer 2

注意 通过平方求幂 不是最优化的方法。作为适用于所有指数值的通用方法，这可能是您能做的最好的事情，但对于特定的指数值，可能有一个需要更少乘法的更好的序列。

例如，如果您想计算 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

没有有效的算法来找到最佳的乘法序列。从 维基百科:

寻找最短加法链的问题无法通过动态规划来解决，因为它不满足最优子结构的假设。也就是说，将幂分解为较小的幂是不够的，每个较小的幂都被最小化地计算，因为较小幂的加法链可能是相关的（以共享计算）。例如，在上面 a15 的最短加法链中，a⁶ 的子问题必须计算为 (a3)2，因为 a3 被重复使用（而不是 a6 = a2(a2)2，这也需要三次乘法）。

Answer 3

如果您需要计算 2 的幂。最快的方法是按功率进行位移位。

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

Answer 4

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

Answer 5

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

Answer 6

如果你想获得 2 的整数次方的值，最好使用 shift 选项：

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

这样效率要高得多。

Answer 7

一个极其特殊的情况是，当您需要说 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 浮点数, ，其他特殊的求幂情况可能会出现。

Answer 8

正如对平方求幂效率的评论的后续。

该方法的优点是它在 log(n) 时间内运行。例如，如果您要计算一些巨大的数据，例如 x^1048575 (2^20 - 1)，则只需执行循环 20 次，而不是使用朴素方法执行 100 万次以上。

此外，就代码复杂性而言，它比按照普拉莫德的建议尝试找到最佳乘法序列更简单。

编辑：

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

Answer 9

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

Answer 10

聚会迟到：

下面是一个解决方案，也涉及 y < 0 尽其所能。

1. 它使用的结果是 intmax_t 以获得最大范围。没有规定不适合的答案 intmax_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;
   }
   

这段代码使用了永远循环 for(;;) 以避免最终 base *= base 在其他循环解决方案中很常见。该乘法是 1) 不需要的，2) 可以是 int*int 溢出即UB。

Answer 11

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

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

Answer 12

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

Answer 13

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

Answer 14

除了 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 - 或任何类型的最大值 - 是一个完全平方数，你可以接受。

Answer 15

我已经实现了记住所有计算功率的算法，然后在需要时使用它们。例如，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);
}

Answer 16

我的情况有点不同，我正在尝试从权力创建一个面具，但我想无论如何我都会分享我找到的解决方案。

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

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

Answer 17

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

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

Answer 18

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

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

  return res;
}

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