本文共 638 字，大约阅读时间需要 2 分钟。

剑指offer面试题16. 数值的整数次方——快速幂

题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数。不得使用库函数，同时不需要考虑大数问题。

输入：x = 2.00000, n = 10输出：1024.00000

思路

• 刚开始用的试模拟的方法，通过循环n个x乘起来，时间复杂度为O(n)。运行时候会超出时间限制。故该方法舍弃！
• 之后看题解了解到快速幂。该方法的详细过程如下：
  
  

代码

• 用的是Java代码，Java 代码中 int32 变量 n 范围是[-2147483648, 2147483647]，因此当 n = -2147483648时执行 n = -n会因越界而赋值出错。解决方法是先将 n存入 long 变量 b，后面用 b 操作即可。

class Solution {    public double myPow(double x, int n) {        if(x==0) return 0;        long b=n;        if(b<0){            x=1/x;            b=-b;        }        double sum=1;        while(b>0){            if((b&1)==1)sum*=x;            x*=x;            b>>=1;        }        return  sum;    }}

转载地址：http://vtgji.baihongyu.com/