平常我们用代码求指数，一般是利用循环实现，例如

求2^10，用C语言可以写为：

int result=1;for(i=0;i<10;i++){    result*=2;}

但是，当指数非常大时，用这种循环无疑会非常慢，例如

求2^10000000000(10个0)，需要循环

2^10000000000(10个0)次，无疑非常浪费时间，尤其在做ACM题目时，时间有限，往往无法达标。

怎么办？我们看下快速求指数(连乘)的原理。

以2^7为例：

(为了方便看，把乘号省略)

2^7：2 2 2 2 2 2 2

，总共需要6次乘法运算

2^7：2 2 2|2 2 2|2，(2^3)*(2^3) *2，而2^3需要2次连乘，因此总共需要4次乘法运算(没看懂的看接下来的注释，看懂的自觉跳过)

=====================上一步的注释===========================

2^3：2*2*2，需要2次乘法运算，通过这两次乘法运算得出2^3的结果

(2^3)*(2^3)，由于2^3结果已知，因此是自乘运算(等效于result*=result;)，算1次乘法运算

(2^3)*(2^3) *2，最后再乘以2，因此总共有4次乘法运算

=====================注释结束==============================

再以2^8为例：

2^2：2|2，(2^1)*(2^1)，2*2一次运算求出2^2

2^4：2 2|2 2，(2^2)*(2^2)，再一次自乘由2^2求出2^4

2^8：2 2 2 2|2 2 2 2 ，(2^4)*(2^4)，再一次自乘由2^4求出2^8

因此快速指数需要3次乘法运算即可。

发现规律了没？

采用二分的思想，每次拿次方数除2，直到商为1终止，把余数和2分次数加起来就可以了

再以2^7为例点明规律

2^7：2 2 2|2 2 2|2，把指数7二分(7个2相乘)，7/2=3（分为两个2^3相乘），7%2=1（余1个2）

2^3：2|2|2，把3均分，3/2=1（两个2^1相乘），3%2=1（余1个2）

2^1已经不能再分(此时3/2=1，即商为1时终止)，因此：

指数/2=1是划分结束标志

总的乘法运算次数=划分次数(2)+余数次数(1)

再以一道ACM题辅助理解：

描述

给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。如2⁴：2*2=2²（第一次乘），2²*2²=2⁴（第二次乘），所以最少共2次；             

输入

第一行m表示有m(1<=m<=100)组测试数据；

每一组测试数据有一整数n（0<n<=10000）;

输出

输出每组测试数据所需次数s;

样例输入

3

2

3

4

样例输出

1

2

2

我用的是二分的方法。每次拿次方数除2，直到商为1终止，把余数和2分次数加起来就可以了。例如：7次
原始：2 2 2 2 2 2 2 
1次：2 2 2 | 2 2 2 | 2 （分了1次，余1，第二次二分只需要取3次方，7/2=3）；
2次：2 |2| 2（又分了1次，余1，此时3/2=1，商为1，不用再二分了）
则共分了2次，两次余1，则2+2=4，需要分4次。
同理8次方分3次

代码如下：

#include 
    
     int main(){
     	int length;
     	int getnum;//输入的次方
     
int mul(long num){//连乘的快捷算法    unsigned long long temp;    if(num==1)        return 2;    temp=mul(num/2);//递归调用    temp=temp*temp*((num%2)?2:1);     if(temp>1000000)//题目只要求后6位数         temp%=1000000;     return temp;}
    

int time=0;//记录2分次数 int remainder=0;//余数不为0的次数 scanf("%d",&length); for(;length>0;length--){ scanf("%d",&getnum); while(getnum!=1){ if(getnum%2) remainder++; time++; getnum/=2; } printf("%d\n",time+remainder); time=0; remainder=0; }}

=====================================================================

原理解释到这，怎么运用呢？以代码展示：

int mul(long num){//连乘的快捷算法，求2^num    unsigned long long temp;    if(num==1)//递归结束条件，1个2相乘，即2^1，上一个指数/2=1的结果        return 2;    temp=mul(num/2);//递归调用    temp=temp*temp*((num%2)?2:1);     return temp;}

由于每一次都是对指数按同样原理划分，以指数/2=1结束，因此采用递归的形式

精华在于

temp=temp*temp*((num%2)?2:1); //有余数：(temp^2)*2，无余数(temp^2)*1

((num%2)?2:1)是对余数的判断，当num%2==1时，乘以1次余下的2，当num%2==0时，使用1，即不变