平方求幂。

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

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

请注意，平方求幂并不是最优的方法。这可能是一种适用于所有指数值的通用方法，但对于特定的指数值，可能有更好的序列，需要更少的乘法。

例如，如果你想计算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

没有有效的算法来找到这个最优的乘法序列。从维基百科:

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a¹⁵ above, the subproblem for a⁶ must be computed as (a³)² since a³ is re-used (as opposed to, say, a⁶ = a²(a²)², which also requires three multiplies).

如果你想得到一个整数的2的幂，最好使用shift选项:

Pow(2,5)可以替换为1<<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);
}

我的情况有点不同，我试图用一种力量创造一个面具，但我想无论如何我都要分享我找到的解决方案。

显然，它只适用于2的幂。

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

下面是一个计算x ** y的O(1)算法，灵感来自这条评论。它适用于32位有符号int。

对于较小的y值，它使用平方求幂。对于较大的y值，只有少数x值的结果不会溢出。这个实现使用一个查找表来读取结果而不进行计算。

对于溢出，C标准允许任何行为，包括崩溃。但是，我决定对LUT索引进行边界检查，以防止内存访问违反，这可能是令人惊讶和不受欢迎的。

伪代码:

If `x` is between -2 and 2, use special-case formulas.
Otherwise, if `y` is between 0 and 8, use special-case formulas.
Otherwise:
    Set x = abs(x); remember if x was negative
    If x <= 10 and y <= 19:
        Load precomputed result from a lookup table
    Otherwise:
        Set result to 0 (overflow)
    If x was negative and y is odd, negate the result

C代码:

#define POW9(x) x * x * x * x * x * x * x * x * x
#define POW10(x) POW9(x) * x
#define POW11(x) POW10(x) * x
#define POW12(x) POW11(x) * x
#define POW13(x) POW12(x) * x
#define POW14(x) POW13(x) * x
#define POW15(x) POW14(x) * x
#define POW16(x) POW15(x) * x
#define POW17(x) POW16(x) * x
#define POW18(x) POW17(x) * x
#define POW19(x) POW18(x) * x

int mypow(int x, unsigned y)
{
    static int table[8][11] = {
        {POW9(3), POW10(3), POW11(3), POW12(3), POW13(3), POW14(3), POW15(3), POW16(3), POW17(3), POW18(3), POW19(3)},
        {POW9(4), POW10(4), POW11(4), POW12(4), POW13(4), POW14(4), POW15(4), 0, 0, 0, 0},
        {POW9(5), POW10(5), POW11(5), POW12(5), POW13(5), 0, 0, 0, 0, 0, 0},
        {POW9(6), POW10(6), POW11(6), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(7), POW10(7), POW11(7), 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(8), POW10(8), 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(9), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {POW9(10), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };

    int is_neg;
    int r;

    switch (x)
    {
    case 0:
        return y == 0 ? 1 : 0;
    case 1:
        return 1;
    case -1:
        return y % 2 == 0 ? 1 : -1;
    case 2:
        return 1 << y;
    case -2:
        return (y % 2 == 0 ? 1 : -1) << y;
    default:
        switch (y)
        {
        case 0:
            return 1;
        case 1:
            return x;
        case 2:
            return x * x;
        case 3:
            return x * x * x;
        case 4:
            r = x * x;
            return r * r;
        case 5:
            r = x * x;
            return r * r * x;
        case 6:
            r = x * x;
            return r * r * r;
        case 7:
            r = x * x;
            return r * r * r * x;
        case 8:
            r = x * x;
            r = r * r;
            return r * r;
        default:
            is_neg = x < 0;
            if (is_neg)
                x = -x;
            if (x <= 10 && y <= 19)
                r = table[x - 3][y - 9];
            else
                r = 0;
            if (is_neg && y % 2 == 1)
                r = -r;
            return r;
        }
    }
}