剑指Offer里和leetcode里都有,剑指offer题目是数值的整数次方，leetcode的题目号是50。

还有一道题也需要快速幂，但是是只取后三位，可能会给一个超级大的指数，这个时候运算其实每次只用后三位去运算，这个题如果不用快速幂和对每次简化的结果进行%1000，保留最后三位的运算，碰到指数大时，必然会指数爆炸，数值溢出。

下面参考自百度百科的概念，指数爆炸的概念：即指数函数的“爆炸性”增长（blow up)，
f(x)=a^x (a为常数，如图中a=2 x为指数) 随着x单位长度的递增，f(x)会呈“爆炸性”增长 ，如图

题目为：求A^B的最后三位数的整数，代码在最下方

普通的幂依次乘效率是很低的O(n)，使用快速幂算法时间复杂度为 O(log2(n)),指数会不断/2。

1.普通算法，遍历乘N次，注意指数负数的话乘的是1/base
2.快速幂算法
(1)当b为偶数时，a^b可以转为a^2的b/2次方。
(2)当b为奇数时，a^b可以转为a^2的b/2次方，再乘以a。

举个例子：

//没简化的
3^10=3*3*3*3*3*3*3*3*3*3

//两两相乘 也就是

3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)

//简化一下
3^10=(3*3)^5

//然后看运算是不是简单很多，指数10缩减为5了
3^10=9^5

//前面的情况是指数为偶数，这时候指数为5，就是指数为奇数的情况了，我们还是先将其拆开

3^10 = 9*9*9*9*9

//再两两括起来,看是不是多出一个9，所以公式那奇数a^b可以转为a^2的b/2次方，再乘以a，这个乘以a就是为了补上这个末尾的9

3^10=(9*9)*(9*9)*9

//继续简化

3^10 = 81^2*9

3^10=6561^1*9

再简化的话指数就为1/2 = 0了，while也退出循环，最后结果就是6561*9

代码如下

//快速幂    
public double FastPower(double base, int exponent) {
        double result = 1;
        while (exponent != 0) {
            if (exponent % 2 == 1) {
                result *= base;
            } else if (exponent % 2 == -1) {
                result *= (1 / base);
            }
            exponent = exponent / 2;
            base = base * base;
        }
        return result;
    }

//普通方法
public double Power(double base, int exponent) {
        double result = 1;
        while (exponent != 0) {
            if (exponent > 0) {
                result *= base;
                exponent--;
            } else if (exponent < 0) {
                result *= (1 / base);
                exponent++;
            }
        }
        return result;
}

//快速幂 求最后三位， 指数不为负数
//思路不过是在每次*=累计结果时，都只保留最后三位，
//如果不这样而是对最后结果%1000，碰到指数大时必然会数值溢出，指数爆炸
public double FastPower(double base, int exponent) {
        double result = 1;
        while (exponent != 0) {
            if (exponent % 2 == 1) {
                result = (result*base) % 1000;
            }  
            exponent = exponent / 2;
            base = (base * base) % 1000;
        }
        return result;
    }