快速幂算法

1.一个重要的结论：

2.x永远在乘以自己，这样就x从1次方变成2次方，然后变成4次方，然后变成8次方.....

 通过位运算不断地取出最后一位是0还是1，来决定此时的x的i次方到底要不要乘到最后的结果里面去（0就表示这个x的i次方不需要乘到最后的结果里面去，1就表示这个x的i次方就要称道最后的结果里面去）

 
public class test
{
    public static int quick_pow(int x,int n)
    {
        int result=1;
        while(n!=0)
        {
            if((n&1)!=0)
            {
                result=result*x;//x起始为x的1次方，然后是x的2次方，x的4次方，x的8次方，x的16次方
            }
            x=x*x;//起始时是x的一次方，然后依次是x的2次方，x的4次方，x的8次方，x的16次方
 
            n=n>>1;//n右移1位，比如1101右移1位，那就变成110，再右移一位就是11，再右移1位就是1，再右移一位就变成0
        }
        return result;
    }
    public static void main(String[] args)
    {
        //底数是x，指数是n，我们需要求出指数n的logn，底数不用管它
        int x=3;
        int n=13;
        System.out.println(quick_pow(x,n));
    }
}

3.时间复杂度

快速幂就是让我们可以快速的求出a的k次方模上p的结果，时间复杂度为O(logk)，其中a,k,p可以为1-10的九次方的任何数

如果采用朴素的方法：

int result=1;
for(int i=1;i<=k;i++)
{
   result=result*a;
}
result=result%p;

 那样时间复杂度就是O(k)

也就是我们可以将时间复杂度从O(k)降低到O(logk)

最后附上acwing 闫学灿的模板：

 例题如下:

1.力扣50 Pow(x,n）

//这道题要注意的是：

（1)底数x是double类型（也就是说有可能是小数），所以最后你的结果result也应该是double类型

  (2)运行下面代码会出错，有一个java int型数据表示范围不对称问题：

java int型数据表数范围不关于0对称_Pr Young的博客-CSDN博客

class Solution 
{
    public double myPow(double x, int n) 
    {
        double result=1.0;
        int flag=0;//用来标志指数n为正数还是负数
 
        if(n==0)    return 1;//指数为0的时候
        if(Math.abs(x-1)<=1e-6)    return  1;//底数为1的时候
        
 
        if(n<0)  
        {
            flag=1;
            n=-n;
        }
        //求x的n次方
        while(n!=0)
        {
            if((n&1)!=0)
            {
                result=result*x;
            }
            x=x*x;
            n=n>>1;
        }
 
        if(flag==1)    result=1/result;
        return result;
    }
}

最后测试用例中,当次数为-2147483648的测试用例无法通过，这是因为：

 int型变量 n 取值范围为： [-2147483648,2147483647]，因此当 n =-2147483648 时执行 n=−n 会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b，后面用 b 操作即可。

class Solution 
{
    public double myPow(double x, int n) 
    {
        double result=1.0;
 
        int flag=0;
        if(n==0)    return 1;
        if(Math.abs(x-1)<=1e-6)    return  1;
       
       
        long b=n;//用b来承接n，这样就不会溢出了
        
        if(b<0)  
        {
            b=-b;
            flag=1;
        }
        //求x的n次方
        while(b!=0)
        {
            if((b&1)!=0)
            {
                result=result*x;
            }
            x=x*x;
            b=b>>1;
        }
 
        if(flag==1)    result=1/result;
        return result;
    }
}