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

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

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

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

小智.. 374

通过平方来表示.

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

    return result;
}

这是在非对称加密中对大量数进行模幂运算的标准方法.

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

这是在非对称加密中对大量数进行模幂运算的标准方法.

---

您应该添加一个"exp"不是负面的检查.目前,此功能将给出错误的答案或永远循环.(取决于>> = on on signed int是否填充零或符号扩展 - 允许C编译器选择任一行为).

---

我写了一个更优化的版本,可以在这里免费下载:https://gist.github.com/3551590在我的机器上,速度提高了约2.5倍.

---

@AkhilJain:这是非常好的C; 为了使它在Java中也有效,分别用`while(exp!= 0)`和`if((exp&1)!= 0)`替换`while(exp)`和`if(exp&1)`.

---

@ZinanXing乘以n次会导致更多的乘法而且速度更慢.该方法通过有效地重用它们来节省乘法.例如,为了计算n ^ 8,"n*n*n*n*n*n*n*n"的朴素方法使用7次乘法.该算法改为计算"m = n*n",然后是"o = m*m",然后是"p = o*o",其中"p"= n ^ 8,只有三次乘法.对于大指数,性能差异很大.

---

你的函数应该有`unsigned exp`,否则正确处理负`exp`.

---

GSL的gsl_sf_pow_int实现了这一点,包括负面案例处理:http://www.gnu.org/software/gsl/manual/html_node/Power-Function.html

---

@AnushreeAcharjee:无论如何,这是一个域名错误.没有C实现可以在整数类型中表示该值.你需要一个28*41535484位类型.

2> Pramod..：

---

请注意,通过平方取幂不是最佳方法.作为适用于所有指数值的通用方法,它可能是最好的,但对于特定的指数值,可能有更好的序列需要更少的乘法.

例如,如果你想计算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²)²,这也需要三次乘法).

---

@JeremySalwen:正如这个答案所述,二进制求幂一般不是最优的方法.目前还没有找到最小乘法序列的有效算法.

---

亚历山大·斯捷潘诺夫和丹尼尔·罗斯在_ [从数学到通用编程](http://www.fm2gp.com)_中对这个确切的问题进行了很好的阐述.这本书应该是每个软件从业者,恕我直言的架子上.

---

@EricPostpischil,这取决于你的申请.通常我们不需要*general*算法来处理所有**数字.参见计算机编程艺术,卷.2:半数值算法

3> Jake..：

---

如果你需要提高2到一个功率.这样做的最快方法是按功率移位.

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

---

`2**0 == 1 << 0 == 1`

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

---

@AnushreeAcharjee当然不是.计算这样的数字将需要任意精度算术.

5> Chris Cudmor..：

---

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

6> Doug T...：

---

一个非常专业的情况是,当你需要说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浮点数,其他特殊的取幂情况可能会出现.

---

基地10？呃不,它是基数2,除非你的意思是10二进制:)

7> 小智..：

---

如果你想得到一个2的整数值,那么使用shift选项总是更好:

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

这样效率更高.

---

雅但它只适用于2或2的倍数.