在 C 中将一个整数提高到另一个整数的幂的最有效方法是什么？
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
Doug T.
问问题
242607 次
19 回答
428
通过平方取幂。
int ipow(int base, int exp)
{
int result = 1;
for (;;)
{
if (exp & 1)
result *= base;
exp >>= 1;
if (!exp)
break;
base *= base;
}
return result;
}
这是在非对称密码学中对大量数字进行模幂运算的标准方法。
于 2008-09-19T12:54:36.193 回答
83
请注意，通过平方取幂不是最佳方法。作为适用于所有指数值的通用方法，这可能是您可以做的最好的事情，但对于特定的指数值，可能会有一个更好的序列，需要更少的乘法。
例如，如果你想计算 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²)² 相反，它也需要三个乘法）。
于 2008-09-20T18:43:33.227 回答
28
如果您需要将 2 提高到一个幂。最快的方法是按功率移位。
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
于 2011-03-17T21:17:42.417 回答
12
这是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;
}
于 2012-05-09T13:55:18.637 回答
8
一个非常特殊的情况是，当您需要说 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 浮点数，其他特殊的求幂情况可能会出现。
于 2008-09-19T12:35:15.927 回答
8
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);
}
于 2008-09-19T14:34:02.023 回答
8
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))
于 2016-01-07T16:25:17.887 回答
6
如果您想将 2 的整数值提高到某个值的幂，最好使用 shift 选项：
pow(2,5)可以替换为1<<5
这效率更高。
于 2012-05-14T07:03:27.027 回答
4
就像对平方求幂效率的评论的跟进一样。
这种方法的优点是它在 log(n) 时间内运行。例如，如果你要计算一些巨大的东西，例如 x^1048575 (2^20 - 1)，你只需要通过循环 20 次，而不是使用幼稚的方法超过 100 万次。
此外，就代码复杂性而言，它比尝试找到最佳乘法序列更简单，这是 la Pramod 的建议。
编辑：
我想我应该在有人为我标记溢出的可能性之前澄清一下。这种方法假设您有某种 hugeint 库。
于 2008-10-02T17:39:02.740 回答
2
晚会迟到：
下面是一个解决方案，它也y < 0尽可能地处理。
- 它使用
intmax_t最大范围的结果。没有规定不适合的答案intmax_t。 powjii(0, 0) --> 1这是这种情况下的常见结果。pow(0,negative)，另一个未定义的结果，返回INTMAX_MAXintmax_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溢出。
于 2015-04-01T17:11:11.153 回答
1
考虑负指数的更通用的解决方案
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);
}
于 2014-06-19T05:30:19.703 回答
1
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
}
于 2021-05-04T00:30:21.160 回答
1
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);
}
是的，它是递归的，但是一个好的优化编译器会优化递归。
于 2021-05-05T23:54:17.970 回答
0
另一种实现（在 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;
}
}
于 2013-12-27T21:24:43.070 回答
0
我使用递归，如果 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);
}
}
于 2015-02-03T14:36:00.173 回答
0
我已经实现了记住所有计算能力然后在需要时使用它们的算法。因此，例如 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);
}
于 2015-08-12T21:16:27.137 回答
0
除了 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_MAXby (int)sqrt(INT_MAX)（在 using 的情况下int）或类似的东西，这应该进行优化，但它更丑陋，而不是 C 常量表达式。由于浮点精度在完美正方形的情况下，也将结果转换sqrt()为 an也不是很好，但我不知道任何实现- 或任何类型的最大值 - 是完美正方形，你可以生活接着就，随即。intINT_MAX
于 2019-03-17T19:17:44.153 回答
-1
我的情况有点不同，我正在尝试从力量中创建一个面具，但我想我还是会分享我找到的解决方案。
显然，它只适用于 2 的幂。
Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
于 2016-08-16T20:55:32.453 回答
-1
如果您在编译时知道指数（并且它是一个整数），您可以使用模板来展开循环。这可以提高效率，但我想在这里演示基本原理：
#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;
}
于 2018-04-07T23:29:26.827 回答