快速幂问题

幂运算是常遇到的一种问题

实现幂运算最简单的思路是暴力循环，复杂度为O(N)

优化–减少乘的次数

首先我们可以不进行n次计算 而是把其中的一些合成一部分来做

例如：求2的10次方，可以求2的2次方 * 2的2次方 * 五次

本来需要进行10次计算，现在需要进行6次

实现–利用二进制迭代实现快速幂

因为计算机是由二进制存储的 所以利用二进制实现快速幂更为方便

例如 10 的二进制表示为 1010

我们计算2的十次方也就是2 的 1010 次方 = 2的8次方+2的2次方

ans：存储计算得到的值

当b大于0的时候循环计算

将b与1做位运算，每次右移一位意思是判断当前位是不是1

#include<bits/stdc++.h>
using namespace std;//二进制实现快速幂
int binaryPow(int a,int b){int ans =1;while(b>0){if (b&1){ans = ans*a; //令ans累计a cout<<"ans:"<<ans<<" ";}a= a*a; cout<<"a:"<<a<<" ";b>>= 1;cout<<"b:"<<b<<" ";cout<<endl;}return ans;
} int main(){int n = 0;n = binaryPow(2,10);cout<<n<<endl;return 0;
}

例如计算2的10次方的计算过程

b b&1 ans a

10 \ 1 a

1010 0 1 a的2次方

101 1 1*a的2次方 a的4次方

10 0 a的2次方 a的8次方

1 1 a的2次方*a的8次方 a的16次方

null

ans = a的10次方