c - 实现基于整数的幂函数 pow(int, int) 的最有效方法

Question

在 C 语言中，将整数乘以另一个整数的幂的最有效方法是什么？

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

Answer 1

平方求幂。

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

    return result;
}

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