二分法求幂

数据结构中二分法运用到求幂提高计算效率方式，算法精简这里做个简单解释及代码

原理自析

如求2^32: 代表底数跟指数，最终结果result

1.判断底数是否为0 为0 则直接输出0；

2.底数不为0时，判断指数是否为0，为0则输出1；

3.底数指数均不为0时，result=1，,进行运算：

A.指数与2求余的结果，如果为1则将result*底数；并且底数（新）= 底数（旧）*底数（旧）

B.指数与2求模的结果，作为新的指数，

3.最终当指数与2就模为0时，输出最终结果result

result只是将指数为1的数据进行最终乘法计算，(黑色字体为result相乘的数据)

2^6  =（2*2）^3

        =（2*2）^1 *（2*2）^2

        =（4）^1 *（4）^2

        =（4）^1 *（4*4）^1

        =（4）^1 *（16）^1

        =64

#include <iostream>

using namespace std;

int a, b;  //利用二分法快速求a^b

int main(int argc, char *argv[]) {

cin >> a >> b;

while (true)

{

int result = 1;

if (a == 0)

cout << 1 << endl;

else if (b == 0)

cout << 1 << endl;

else

{

while (b != 0)

{

if (b % 2 == 1)

{

result *= a;

}

a *= a;

b /= 2;

}

}

cout << "结果:" << result << endl;

cin >> a >> b;

}

return 0;

备注：以上二分法基本思路完成，通过参考资料给指数求余和求模，其实可以通过位运算进一步提高计算性能

b % 2等价于 b & 1，因为B为偶数时，其二进制最后一位一定是0，B为奇数时，其二进制最后一位一定是1；因此做与计算为0则为偶数，计算为1则为奇数

b / 2 等价于 b >> 1 ,因为B/2相当于将B的二进制每一位向后移动1位；

参考进阶资料公式 用于获取最终结果后三位

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p ) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

while(b>0) {

if(b&1) {//此处等价于if(b%2==1)

result = result * a%1000;}

b>>=1;//此处等价于b=b/2

a= (a* a) %1000;

 }

return result;