快速幂
程序员文章站
2022-07-12 16:10:30
...
快速幂的算法:
要是想对于一些比较小的数的话就可以直接调用数学函数来实现就可以,但是遇到相对大数的话就需要用另一种方法利用二进制来实现快速幂运算。
我们可以先看一个简单的幂运算来理解一下如何用二进制来实现快速幂;
自己模拟一边就可以理解
#include <iostream>
using namespace std;
int pow(int a,int b)
{
int ans=1;
while(b!=0) //b!=0就继续去循环
{
if(b&1!=0) //就是b用二进制表示最后一位不是0就执行下一步运算
ans=ans*a;
a=a*a;
cout<<ans<<endl;
cout<<a<<endl;
b=b>>1; //二进制往前取一位
cout<<b<<endl;
}
return ans;
}
int main ()
{
int x=pow(3,11);
printf ("%d\n",x);
return 0;
}