计算 x^n 时间复杂度为O(long N)的算法

计算 xⁿ 很容易， 直接用一个 for 循环就就可以实现：

double pow(double x, int n)
{
    int i;
    for (i=0; i<n; i++){
        x *= x;
    }
    
    return x;
}

今天在百度上发现了一个更快的算法， 它的时间复杂度是 O(long N) ：

double pow(double x, int n)
{
    double temp = x;
    double result = 1;
    
    while (n){
        if (n%2){
            result = result * temp;
        }
        n = n / 2;
        temp *= temp;   // 循环次数：temp的值 1:x^2, 2:x^4, 3:x^8……;
    }
    
    return result;
}

思路：假如要计算3⁵； 先可以将 5 转换成二进制为 101； 而 101 = (2²+2¹)；
所以：3⁵ = 3^(22+21) = 3⁴ * 3¹