二分快速幂

递归法:

// fun(a, b): 求a^b
int fun(int a, int b){
    // 当b == 1时，a^1 = a
    if(b == 1) return a;
    // 当b是偶数  fun(a, b) =>  fun(a*a , b/2)
    if(b%2 == 0) return fun(a*a , b/2);
    // 当b是奇数
    if(b%2 == 1) return fun(a , b-1)*a;
}

循环2

int fun3(int a, int b){
    int res = 1;
    while(b){
        // 当b是奇数
        if(b%2 == 1) res = res*a;
        // 当b是偶数
        a = a*a;
        b = b/2;
    }
return res;
}

循环1

int fun_(int a, int b){
int res = 1;
while(b){
// 当b是奇数
if(b%2 == 1){
res = res*a;
b--;
}
// 当b是偶数
else{
a = a*a;
b = b/2;
}
}
return res;
}