快速幂运算 与 快速幂取余

     在很多情况下，我们队数据的处理的时候需要进行幂运算，但是如果进行n次的话时间复杂度是O（n）, 可能会超时， 所以今天学习一种能够优化幂运算的算法 ------- 快速幂运算，能有效的将时间复杂度降低到O（log（n））

    快速幂运算简介：

             快速幂运算，可以看做是按位进行的一种取幂运算（二进制的伟大之处）， 先看一个例子吧， 以2 的4次方为例：

       从上面的式子中，我们可以看出来，当指数的某一位是0的时候，我们可以忽略掉这一位，当指数不为0的时候乘上我们累计的底数(乘的是2^2);

快速幂 Code :

int Pow(int x, int n)
{
    int ans = 1;
    int base = x;
    while(n > 0)
    {
        if(n & 1) //指数该位不为0
            ans *= base;
        base *= base; //累乘
        n >>= 1; // 右移1位，抹平后面还有的数字
    }
    return ans;
}

 在有的时候我们需要对产生的解进行取余，如过底数和指数都特别大呐？取余岂不是特别费事，这时候我们就需要运用快速幂取余公式了

      （a * b）% mod = ( ( a % mod ) * ( b % mod ) ) % mod ;

快速幂取模Code :

int Pow(int a, int b, int mod) //底数， 指数， 模
{
    int ans = 1;
    int base = a;
    while(b != 0)
    {
        if(b & 1)
            ans = ((ans % mod) * (base % mod)) % mod;
        base = ((base%mod) * (base%mod))% mod;
        b >>= 1;
    }
    return ans;
}

最后

以上就是谦让玫瑰为你收集整理的快速幂运算 与 快速幂取余的全部内容，希望文章能够帮你解决快速幂运算 与 快速幂取余所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。