蒟蒻学习快速幂笔记

佚名 6年前 (2019-04-14) 随笔 679人围观抢沙发百度已收录

我基本是在刷题中学习的算法，所以基本学的算不上系统，也可能说不上全面

为了防止遗忘，学习了的东西就通过博客记录下来吧。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

快速幂

旨在减少计算次数，可以将O(n)--->O(logn);

减少时间复杂度

a^b

例如：2^13:一般方法是循环相乘13次，但是利用二进制，可以将幂次13改写为二进制1101；于是2^13--->2^(1*2^0+0*2^1+1*2^2+1*2^3);只需要计算4次！！！

代码：

int fast_pow(int a,int b)
{
    int ans=1;int base=a;
    while(b!=0)
    {
        if(b&1!=0)//b二进制上最后一位为1，不为0
            ans*=base;
        base*=base;
        b>>=1;//b的二进制数向右移一位
        return ans;          
    }