快速幂算法（普通幂算法进阶版）

具体要求：求a^b的后三位数。

• 减少指数大小，减少循环次数。

以 2 10 2^{10} 210为例。

当指数为偶数时，先将指数除以二，再将底数平方。

2 10 = 4 5 2^{10}=4^{5} 210=45

当指数为奇数时，将指数减一再除以二，提出底数，再将底数平方。

4 5 = 4 × 1 6 2 4^{5}=4times 16^{2} 45=4×162

一直运算下去直至： 2 10 = 4 × 25 6 1 2^{10}=4times 256^{1} 210=4×2561

这样，循环操作从原来的10次减少到4次。快速幂运算极大提高了算法的运行速度。

• 具体代码如下：

#include
#include
using namespace std;
long long fastpower(long long base,long long power)
{

    long long result=1;
    while(power>0)
    {
        if(power%2==0)
        {
            power/=2;
            base=base*base%1000;
        }
        else
        {
            power-=1;
            result=base*result%1000;
            power/=2;
            base=(base*base)%1000;
        }
    }
    return result;
}
int main()
{
    clock_t start,end;
    long long base,power;
    cout<<"请输入a的值和b的值：n";
    cin>>base>>power;
    start=clock();
    cout< 
位运算对代码运行速度进行优化: 
if…else语句中存在重复的语句，对重复语句进行优化。
 
// 重复语句
power/=2;
base=(base*base)%1000;

// 优化之后
if(power%2==1)
{
    power-=1;
    result=base*result%1000;
}
power/=2;
base=(base*base)%1000;
 
当power为奇数时，power不在减1除2变换成偶数，根据C++编译机制直接将power除2，会自动向下取整。
 
// 优化之后
if(power%2==1)
{
    result=base*result%1000;
}
power/=2;
base=(base*base)%1000;
 
用位运算取代除运算，由于位运算是直接使用通过机器指令实现，运算速度快于其他运算。
 
//优化之后
if(power&1)
{
    result=base*result%1000;
}
power>>=1;
base=(base*base)%1000;
 
优化之后的具体代码如下
 
#include
#include
using namespace std;
long long fastpower(long long base,long long power)
{

    long long result=1;
    while(power>0)
    {
        if(power&1)
        {
            result=base*result%1000;
        }
        power>>=1;
        base=(base*base)%1000;
     }
    return result;
}
int main()
{
    clock_t start,end;
    long long base,power;
    cout<<"请输入a的值和b的值：n";
    cin>>base>>power;
    start=clock();
    cout< 
power&1当power为偶数时该结果为0，为奇数时为1。