你如何在 C# 中做*整数* 取幂？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/383587/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do you do *integer* exponentiation in C#?
提问by Roman Starkov
The built-in Math.Pow()function in .NET raises a doublebase to a doubleexponent and returns a doubleresult.
Math.Pow().NET 中的内置函数将double基数提升为double指数并返回double结果。
What's the best way to do the same with integers?
对整数执行相同操作的最佳方法是什么？
Added: It seems that one can just cast Math.Pow()result to (int), but will this always produce the correct number and no rounding errors?
补充：似乎可以将Math.Pow()结果转换为（int），但这是否总是产生正确的数字并且没有舍入错误？
采纳答案by Vilx-
A pretty fast one might be something like this:
一个非常快的可能是这样的：
int IntPow(int x, uint pow)
{
int ret = 1;
while ( pow != 0 )
{
if ( (pow & 1) == 1 )
ret *= x;
x *= x;
pow >>= 1;
}
return ret;
}
Note that this does not allow negative powers. I'll leave that as an exercise to you. :)
请注意，这不允许负权力。我将把它留给你作为练习。:)
Added:Oh yes, almost forgot - also add overflow/underflow checking, or you might be in for a few nasty surprises down the road.
补充：哦，是的，差点忘了 - 还要添加上溢/下溢检查，否则您可能会遇到一些令人讨厌的惊喜。
回答by John D. Cook
回答by bh213
Use double version, check for overflow (over max int or max long) and cast to int or long?
使用双版本，检查溢出（超过 max int 或 max long）并转换为 int 或 long？
回答by Charles Bretana
Using the math in John Cook's blog link,
使用约翰库克博客链接中的数学，
public static long IntPower(int x, short power)
{
if (power == 0) return 1;
if (power == 1) return x;
// ----------------------
int n = 15;
while ((power <<= 1) >= 0) n--;
long tmp = x;
while (--n > 0)
tmp = tmp * tmp *
(((power <<= 1) < 0)? x : 1);
return tmp;
}
to address objection that the code will not work if you change the type of power, well... leaving aside the point that anyone who changes code they don't understand and then uses it without testing.....
but to address the issue, this version protects the foolish from that mistake... (But not from a myriad of others they might make) NOTE: not tested.
如果您改变权力的类型，代码将无法工作，以解决反对意见，好吧......撇开任何改变代码的人他们不理解然后未经测试就使用它的观点......
但要解决这个问题问题，这个版本保护愚蠢的人免受那个错误......（但不是他们可能犯的无数其他错误）注意：未经测试。
public static long IntPower(int x, short power)
{
if (power == 0) return 1;
if (power == 1) return x;
// ----------------------
int n =
power.GetType() == typeof(short)? 15:
power.GetType() == typeof(int)? 31:
power.GetType() == typeof(long)? 63: 0;
long tmp = x;
while (--n > 0)
tmp = tmp * tmp *
(((power <<= 1) < 0)? x : 1);
return tmp;
}
Also try this recursive equivalent (slower of course):
也试试这个递归的等价物（当然更慢）：
public static long IntPower(long x, int power)
{
return (power == 0) ? x :
((power & 0x1) == 0 ? x : 1) *
IntPower(x, power >> 1);
}
回答by Evan Moran
My favorite solution to this problem is a classic divide and conquer recursive solution. It is actually faster then multiplying n times as it reduces the number of multiplies in half each time.
我最喜欢这个问题的解决方案是经典的分而治之的递归解决方案。它实际上比乘 n 次要快，因为它每次将乘法次数减少一半。
public static int Power(int x, int n)
{
// Basis
if (n == 0)
return 1;
else if (n == 1)
return x;
// Induction
else if (n % 2 == 1)
return x * Power(x*x, n/2);
return Power(x*x, n/2);
}
Note: this doesn't check for overflow or negative n.
注意：这不会检查溢出或负 n。
回答by mini-me
How about:
怎么样：
public static long IntPow(long a, long b)
{
long result = 1;
for (long i = 0; i < b; i++)
result *= a;
return result;
}
回答by 3dGrabber
LINQ anyone?
LINQ有人吗？
public static int Pow(this int bas, int exp)
{
return Enumerable
.Repeat(bas, exp)
.Aggregate(1, (a, b) => a * b);
}
usage as extension:
作为扩展使用：
var threeToThePowerOfNine = 3.Pow(9);
回答by Sunsetquest
Two more...
还有两个...
public static int FastPower(int x, int pow)
{
switch (pow)
{
case 0: return 1;
case 1: return x;
case 2: return x * x;
case 3: return x * x * x;
case 4: return x * x * x * x;
case 5: return x * x * x * x * x;
case 6: return x * x * x * x * x * x;
case 7: return x * x * x * x * x * x * x;
case 8: return x * x * x * x * x * x * x * x;
case 9: return x * x * x * x * x * x * x * x * x;
case 10: return x * x * x * x * x * x * x * x * x * x;
case 11: return x * x * x * x * x * x * x * x * x * x * x;
// up to 32 can be added
default: // Vilx's solution is used for default
int ret = 1;
while (pow != 0)
{
if ((pow & 1) == 1)
ret *= x;
x *= x;
pow >>= 1;
}
return ret;
}
}
public static int SimplePower(int x, int pow)
{
return (int)Math.Pow(x, pow);
}
I did some quick performance testing
我做了一些快速的性能测试
mini-me : 32 ms
Sunsetquest(Fast) : 37 ms
Vilx : 46 ms
Charles Bretana(aka Cook's): 166 ms
Sunsetquest(simple) : 469 ms
3dGrabber (Linq version) : 868 ms
迷你我：32 毫秒
Sunsetquest（快速）：37 毫秒
维尔克斯：46 毫秒
Charles Bretana（又名库克的）：166 毫秒
Sunsetquest（简单）：469 毫秒
3dGrabber（Linq 版本）：868 毫秒
(testing notes: intel i7 2nd gen, .net 4, release build, release run, 1M different bases, exp from 0-10 only)
（测试说明：intel i7 2nd gen、.net 4、发布版本、发布运行、1M 不同的基础、仅 0-10 的 exp）
Conclusion: mini-me's is the best in both performance and simplicity
结论：mini-me 的性能和简单性都是最好的
very minimal accuracy testing was done
完成了非常小的精度测试
回答by Claudio
I cast the result into int, like this:
我将结果转换为 int，如下所示：
double exp = 3.0;
int result = (int)Math.Pow(2.0, exp);
In this case, there are no rounding errors because base and exponent are integer. The result will be integer too.
在这种情况下，没有舍入错误，因为基数和指数是整数。结果也将是整数。
回答by Ralph
For a short quick one-liner.
对于一个简短的快速单线。
int pow(int i, int exp) => (exp == 0) ? 1 : i * pow(i, exp-1);
There are no negative exponent nor overflow checks.
没有负指数或溢出检查。
