除了Elias的答案，当使用有符号整数实现时，会导致未定义行为，当使用无符号整数实现时，会导致高输入的不正确值，

下面是平方求幂的修改版本，它也适用于有符号整数类型，并且不会给出错误的值:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

使用该函数的注意事项:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

如果将发生任何溢出或换行，则返回0;

I used int64_t, but any width (signed or unsigned) can be used with little modification. However, if you need to use a non-fixed-width integer type, you will need to change SQRT_INT64_MAX by (int)sqrt(INT_MAX) (in the case of using int) or something similar, which should be optimized, but it is uglier, and not a C constant expression. Also casting the result of sqrt() to an int is not very good because of floating point precission in case of a perfect square, but as I don't know of any implementation where INT_MAX -or the maximum of any type- is a perfect square, you can live with that.

如果要取2的a次方。最快的方法是按幂位移位。

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

迟到的人:

下面是一个尽可能处理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。

O(log N)的解决方案在Swift…

// Time complexity is O(log N)
func power(_ base: Int, _ exp: Int) -> Int { 

    // 1. If the exponent is 1 then return the number (e.g a^1 == a)
    //Time complexity O(1)
    if exp == 1 { 
        return base
    }

    // 2. Calculate the value of the number raised to half of the exponent. This will be used to calculate the final answer by squaring the result (e.g a^2n == (a^n)^2 == a^n * a^n). The idea is that we can do half the amount of work by obtaining a^n and multiplying the result by itself to get a^2n
    //Time complexity O(log N)
    let tempVal = power(base, exp/2) 

    // 3. If the exponent was odd then decompose the result in such a way that it allows you to divide the exponent in two (e.g. a^(2n+1) == a^1 * a^2n == a^1 * a^n * a^n). If the eponent is even then the result must be the base raised to half the exponent squared (e.g. a^2n == a^n * a^n = (a^n)^2).
    //Time complexity O(1)
    return (exp % 2 == 1 ? base : 1) * tempVal * tempVal 

}

下面是一个计算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;
        }
    }
}

我注意到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进制的范例中。

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