你如何在C#中进行*整数*取幂？

Question

Math.Pow().NET中的内置函数double为double指数提供基础并返回double结果.

使用整数执行相同操作的最佳方法是什么？

补充:似乎可以将Math.Pow()结果转换为(int),但这总是产生正确的数字而没有舍入错误？

Answer 1

一个非常快的可能是这样的:

int IntPow(int x, uint pow)
{
    int ret = 1;
    while ( pow != 0 )
    {
        if ( (pow & 1) == 1 )
            ret *= x;
        x *= x;
        pow >>= 1;
    }
    return ret;
}

请注意,这不允许负功率.我会把它作为练习留给你.:)

补充:哦,是的,差点忘了 - 还要添加溢出/下溢检查,否则你可能会遇到一些令人讨厌的惊喜.

Answer 2

LINQ有人吗？

public static int Pow(this int bas, int exp)
{
    return Enumerable
          .Repeat(bas, exp)
          .Aggregate(1, (a, b) => a * b);
}

用作扩展名:

var threeToThePowerOfNine = 3.Pow(9);

Answer 3

使用John Cook的博客链接中的数学,

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

如果你改变了电源的类型,那么代码就不会起作用的反对意见......撇开任何更改代码的人,他们不理解然后在没有测试的情况下使用它......
但是要解决这个问题.问题,这个版本保护愚蠢的人免受这个错误......(但不是来自他们可能做的其他人)注意:没有经过测试.

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

也尝试这个递归等价物(当然慢):

    public static long IntPower(long x, int power)
    {
        return (power == 0) ? x :
            ((power & 0x1) == 0 ? x : 1) *
                IntPower(x, power >> 1);
    }

Answer 4

lolz,怎么样:

public static long IntPow(long a, long b)
{
  long result = 1;
  for (long i = 0; i < b; i++)
    result *= a;
  return result;
}

Answer 5

这是一篇博客文章,解释了将整数提升为整数幂的最快方法.正如其中一条评论指出的那样,其中一些技巧是内置于芯片中的.

Answer 6

非常有趣.. .net 5.0 SimplePower() 现在快 350 倍。我会说在便携性/性能/可读性方面最好......

    public static int SimplePower(int x, int pow)
    {
        return (int)Math.Pow(x, pow);
    }

这是我过去建造的另一个速度很快的...

    public static int PowerWithSwitch(int x, int pow)
    {
        switch ((uint)pow)
        {
            case 0: return 1;
            case 1: return x;
            case 2: return x * x;
            case 3: return x * x * x;
            case 4: { int t2 = x * x; return t2 * t2; }
            case 5: { int t2 = x * x; return t2 * t2 * x; }
            case 6: { int t3 = x * x * x; return t3 * t3; }
            case 7: { int t3 = x * x * x; return t3 * t3 * x; }
            case 8: { int t3 = x * x * x; return t3 * t3 * x * x; }
            case 9: { int t3 = x * x * x; return t3 * t3 * t3; }
            case 10: { int t3 = x * x * x; return t3 * t3 * t3 * x; }
            case 11: { int t3 = x * x * x; return t3 * t3 * t3 * x * x; }
            case 12: { int t3 = x * x * x; return t3 * t3 * t3 * t3; }
            case 13: { int t3 = x * x * x; return t3 * t3 * t3 * t3 * x; }
            case 14: { int t4 = x * x * x * x; return t4 * t4 * t4 * x * x; }
            case 15: { int t4 = x * x * x * x; return t4 * t4 * t4 * x * x * x; }
            case 16: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4; }
            case 17: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * x; }
            case 18: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * x * x; }
            case 19: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * x * x * x; }
            case 20: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4; }
            case 21: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * x; }
            case 22: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * x * x; }
            case 23: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * x * x * x; }
            case 24: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4; }
            case 25: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * x; }
            case 26: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * x * x; }
            case 27: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * x * x * x; }
            case 28: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * t4; }
            case 29: { int t4 = x * x * x * x; return t4 * t4 * t4 * t4 * t4 * t4 * t4 * x; }
            default:
                if (x == 0)
                    return 0;
                else if (x == 1)
                    return 1;
                else
                    return (x % 1 == 0) ? int.MaxValue : int.MinValue;
        }
        return 0;
    }

性能测试 (.Net 5)

• MathPow（Sunsetquest）：11 毫秒（.net 4 = 3693 毫秒）<- 快 350 倍！！！

• PowerWithSwitch(Sunsetquest)：145 毫秒（.net 4 = 298 毫秒）

• 维尔克斯：148 毫秒（.net 4 = 320 毫秒）

• Evan Moran-递归除法：249 毫秒（.net 4 = 644 毫秒）

• 迷你我：288 毫秒（.net 4 = 194 毫秒）

• Charles Bretana（又名库克的）：536 毫秒（.net 4 = 950 毫秒）

• LINQ 版本：4416 毫秒（.net 4 = 3693 毫秒）

（测试说明：AMD Threadripper Gen1、.Net 4 & 5、发布版本、未附加调试器、bases：0-100k、exp：0-10）

注意：在上述测试中几乎没有进行准确性检查。