二分法求冪
數(shù)據(jù)結(jié)構(gòu)中二分法運用到求冪提高計算效率方式，算法精簡這里做個簡單解釋及代碼
原理自析
如求2^32: 代表底數(shù)跟指數(shù)尿这，最終結(jié)果result
1.判斷底數(shù)是否為0 為0 則直接輸出0朽缎；
2.底數(shù)不為0時稠集，判斷指數(shù)是否為0撮执，為0則輸出1；
3.底數(shù)指數(shù)均不為0時沙兰，result=1氓奈，,進行運算：
A.指數(shù)與2求余的結(jié)果，如果為1則將result*底數(shù)鼎天；并且底數(shù)（新）= 底數(shù)（舊）*底數(shù)（舊）
B.指數(shù)與2求模的結(jié)果舀奶，作為新的指數(shù)，
3.最終當指數(shù)與2就模為0時训措，輸出最終結(jié)果result
result只是將指數(shù)為1的數(shù)據(jù)進行最終乘法計算伪节，(黑色字體為result相乘的數(shù)據(jù))
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 << "結(jié)果:" << result << endl;
cin >> a >> b;
}
return 0;
備注：以上二分法基本思路完成，通過參考資料給指數(shù)求余和求模绩鸣，其實可以通過位運算進一步提高計算性能
b % 2等價于 b & 1怀大，因為B為偶數(shù)時，其二進制最后一位一定是0呀闻，B為奇數(shù)時化借，其二進制最后一位一定是1；因此做與計算為0則為偶數(shù)捡多，計算為1則為奇數(shù)
b / 2 等價于 b >> 1 ,因為B/2相當于將B的二進制每一位向后移動1位蓖康；
參考進階資料公式 用于獲取最終結(jié)果后三位
(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;
