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

给C中的另一个整数赋予整数的最有效方法是什么？

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

Answer 1

指数乘以平方。

 int ipow(int base, int exp) { int result = 1; while (exp) { if (exp & 1) result *= base; exp >>= 1; base *= base; } return result; } 

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

Answer 2

请注意， 通过平方的指数并不是最优的方法。 对于所有指数值，这可能是您可以做的最好的一种常规方法，但对于特定的指数值，可能会有更好的序列，需要更less的乘法。

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

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

这是总共6次乘法。

事实certificate，这可以通过使用“正好”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 

没有有效的algorithm来find这个最佳的乘法序列。 维基百科 ：

寻找最短加法链的问题不能通过dynamic规划来解决，因为它不能满足最优子结构的假设。 也就是说，将功率分解成更小的功率是不够的，每个功率的计算最小，因为较小功率的加法链可能是相关的（以共享计算）。 例如，在上述第十五条的最短加法链中，由于a³被重新使用（相对于a⁶=a²（a²）2），a⁶的子问题必须计算为（a³）²，这也需要三次相乘）。

Answer 3

这是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 4

如果你需要提高2的权力。 最快的方法是通过权力位移。

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

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

一个非常特殊的情况是，当你需要对y表示2 ^（ – 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; uf = 2.0; // Change the exponent part of the float u.brokenOut.exponent += (exponent - 1); return (uf); } 

通过使用double作为基types，可以获得更多的2的幂。 （非常感谢评论者帮助把这篇文章打散）。

也有可能学习更多的关于IEEE浮点数 ，其他特殊情况下的指数可能会出现。

Answer 8

正如跟随平方的效率幂的评论。

这种方法的优点是它在log（n）时间运行。 例如，如果你打算计算一些很大的东西，比如x ^ 1048575（2 ^ 20 – 1），那么你只需要循环20次，而不是100万次。

而且，就代码复杂性而言，比试图find最佳的乘法序列还要简单，就是Pramod的build议。

编辑：

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

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基础工作 。

 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

晚会之后：

下面是一个解决scheme，也尽可能处理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(;;)的永久循环来避免其他循环解决scheme中的最终base *= base 。 这个乘法是1）不需要和2）可以是int*int溢出这是UB。

Answer 11

一个更多的实现（Java）。 可能不是最有效的解决scheme，但迭代次数与指数解决scheme相同。

 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 12

考虑负指数的更通用的解决scheme

 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 13

我已经实现了记忆所有计算能力的algorithm，然后在需要时使用它们。 因此，例如x ^ 13等于（x ^ 2）^ 2 ^ 2 * x ^ 2 ^ 2 * x其中x ^ 2 ^ 2从表中取而不是再次计算它。 所需的乘法次数是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 14

我使用recursion，如果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 15

我的情况有点不同，我试图用权力来创build一个面具，但我想我会分享我find的解决scheme。

显然，它只适用于2的权力。

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

Answer 16

我已经find了一个比起for循环这个巨大的开关语句有点快的方法。 好吧，也许这不是最简单的方法，但有一个范围从-50（或另一个数字，取决于您的需要）到+50的交换机，并在每个有像return number * number * ...; break; return number * number * ...; break; 等等。 对于具有双精度数字的1M运行，这需要0.001秒。 对于整数它更快。 你可以在这里find一个示例标题

我能想到的唯一缺陷就是caching内存，有这样一个大声明你可能会遇到一些问题，但这只是假设。

但是，您仍然可以限制交换机的大小，通常功率不会高于20-25。

Answer 17

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

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

编辑：正如已经指出，这不是最有效的方式…只要你定义效率作为CPU周期，我认为是公平的。