快速求幂算法

在写一个数的幂运算的时候我们通常会想到比较直观的O(N)算法，代码如下

#include<stdio.h>
int main() {
    int pow = 5;//指数
    int num = 2;//底
    int res=1;//结果
    while (pow>0) {
        res *= num;
        pow--;
    }
    printf("%d", res);
}

最近在做数据结构习题的时候学习到了一中快速求幂算法，时间复杂度为log2(N).
这个算法运用到了二进制数的除2运算，二进制的除法与十进制基本类似，下面举一个例子23/2,结果为1011余1

所以23（10111）/2（10）=（11）1011，这就意味每除一次2便可以去掉末位的1，23（10111）%2（10）=1.
在计算2^23时我们就可以通过计算2^16(10000),2^4(100),2^2(10),2^1(1)然后相乘，将其分解成了这几个部分相乘。
下面是代码实现

void QuickPower(int Coefficient,int Exponent) {
    int result = 1;
    while (Exponent!=0) {
        if (Exponent % 2) 
            result *= Coefficient;
        Coefficient *= Coefficient;
        Exponent = Exponent / 2;
    }
    return result;
}

最后

以上就是风中手机最近收集整理的关于快速求幂算法的全部内容，更多相关快速求幂算法内容请搜索靠谱客的其他文章。