How do you do *integer* exponentiation in C#?

问题:

The built-in Math.Pow() function in .NET raises a double base to a double exponent and returns a double result.

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?

回答1:

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.

回答2:

LINQ anyone?

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

回答3:

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

回答4:

lolz, how about:

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

回答5:

Here's a blog post that explains the fastest way to raise integers to integer powers. As one of the comments points out, some of these tricks are built into chips.

回答6:

Use double version, check for overflow (over max int or max long) and cast to int or long?

回答7:

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.

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.

回答8:

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

(testing notes: intel i7 2nd gen, .net 4, release build, release run, 1M different bases, exp from 0-10 only)

Conclusion: mini-me's is the best in both performance and simplicity

very minimal accuracy testing was done

回答9:

I cast the result into int, like this:

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.

回答10:

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.