迟到的人:

下面是一个尽可能处理y < 0的解。

It uses a result of intmax_t for maximum range. There is no provision for answers that do not fit in intmax_t. powjii(0, 0) --> 1 which is a common result for this case. pow(0,negative), another undefined result, returns INTMAX_MAX intmax_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(;;)，以避免在其他循环解决方案中常见的最终基数*=基数。这个乘法是1)不需要的，2)可能是int*int溢出，也就是UB。

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

例如，如果你想计算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^(-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浮点数的知识，其他幂运算的特殊情况可能会出现。

我注意到gnu-GMP的标准指数平方算法有些奇怪:

我实现了两个几乎相同的函数——一个是幂模函数，使用最普通的二进制指数平方算法，

标签______2 ()

然后另一个基本相同的概念，但重新映射为每轮除以10，而不是除以2，

标签______10 ()

.

 ( time ( jot - 1456 9999999999 6671 | pvE0 | 

gawk -Mbe '
function ______10(_, __, ___, ____, _____, _______) {
      __ = +__
    ____ = (____+=_____=____^= \
           (_ %=___=+___)<_)+____++^____—

    while (__) {
        if (_______= __%____) {
            if (__==_______) {
                return (_^__ *_____) %___
            }
            __-=_______
            _____ = (_^_______*_____) %___
        }
        __/=____
        _ = _^____%___
    }
}
function ______2(_, __, ___, ____, _____) {
    __=+__
    ____+=____=_____^=(_%=___=+___)<_
    while (__) {
        if (__ %____) {
            if (__<____) {
                return (_*_____) %___
            }
            _____ = (_____*_) %___
            --__
        }
        __/=____
        _= (_*_) %___
    }
} 
BEGIN {
    OFMT = CONVFMT = "%.250g"

    __ = (___=_^= FS=OFS= "=")(_<_)

    _____ = __^(_=3)^--_ * ++_-(_+_)^_
    ______ = _^(_+_)-_ + _^!_

    _______ = int(______*_____)
    ________ = 10 ^ 5 + 1
    _________ = 8 ^ 4 * 2 - 1
}

GNU Awk 5.1.1, API: 3.1 (GNU MPFR 4.1.0, GNU MP 6.2.1)

.

($ + + NF = ______10(_ = ___美元,NR %________ +_________,_______*(_- 11))) ^ !___“

     out9: 48.4MiB 0:00:08 [6.02MiB/s] [6.02MiB/s] [ <=> ]
      in0: 15.6MiB 0:00:08 [1.95MiB/s] [1.95MiB/s] [ <=> ]
( jot - 1456 9999999999 6671 | pvE 0.1 in0 | gawk -Mbe ; )  

8.31s user 0.06s system 103% cpu 8.058 total
ffa16aa937b7beca66a173ccbf8e1e12  stdin

($ + + NF = ______ 2(_ = ___美元,NR %________ +_________,_______*(_- 11))) ^ !___“

     out9: 48.4MiB 0:00:12 [3.78MiB/s] [3.78MiB/s] [<=> ]
      in0: 15.6MiB 0:00:12 [1.22MiB/s] [1.22MiB/s] [ <=> ]
( jot - 1456 9999999999 6671 | pvE 0.1 in0 | gawk -Mbe ; )  

13.05s user 0.07s system 102% cpu 12.821 total
ffa16aa937b7beca66a173ccbf8e1e12  stdin

由于一些非常违反直觉和我不知道的原因，对于我投入的各种各样的输入，div-10变体几乎总是更快。这是两个哈希值之间的匹配，这让它真正令人困惑，尽管计算机显然没有内置在10进制的范例中。

我是否在代码/方法中遗漏了一些关键或明显的东西，可能会以令人困惑的方式歪曲结果?谢谢。

更一般的解决方案考虑负指数

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

另一个实现(在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;
    }       
}