剑指offer面试题16：数值的整数次方

题目描述：实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。

示例 1：输入：x = 2.00000, n = 10         输出：1024.00000
示例 2：输入：x = 2.10000, n = 3           输出：9.26100
示例 3：输入：x = 2.00000, n = -2          输出：0.25000       解释：2^-2 = 1/2^2 = 1/4 = 0.25

使用递归的方法：                                                                                                                           

n = 0 时，任何 x 都返回 1
n = 1 时，返回 x
n = -1 时，返回 1 / x

对于其他n值：                                                                                                                               

当 n 为偶数时，myPow(x,n) = myPow(x,n/2)* myPow(x,n/2)
当 n 为奇数时：myPow(x,n) = myPow(x,(n-1)/2) * myPow(x,(n-1)/2) * x

class Solution {
public:
    double myPow(double x, int n) 
    {
        // 递归出口
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -1) return 1/x;

        // n奇数
        if(n%2 != 0) 
        {
            return x*myPow(x,n-1);
        }
        
        //n偶数
        if(n%2 == 0)
        {
            double half = myPow(x,n/2);
            return half*half;
        }
        return 0;
    }
};

class Solution {
public:
    double myPow(double x, int n) 
    {
        // 递归出口
        if(n == 0) return 1;
        if(n == 1) return x;
        if(n == -1) return 1/x;

        //将偶数和奇数合并，奇数%2=1（余数），偶数%2=0
        double half = myPow(x,n/2);
        double mod = myPow(x,n%2);
        return half*half*mod;
    }
};

class Solution {
public:
    double myPow(double x, int n) 
    {
       long long N=n; //防止溢出
       return N>=0 ? quickMul(x,N) : 1.0/quickMul(x,-N);
    }

    double quickMul(double x,int n)
    {
        if(n == 0) return 1.0;

        double y = quickMul(x,n/2);
        return n%2 == 0 ? y*y : y*y*x;
    }
};

基于以上原理，我们在计算一个数的多次幂时，可以先判断其幂次的奇偶性，然后：

• 如果幂次为偶直接 base(底数) 作平方，power(幂次) 除以2

• 如果幂次为奇则底数平方，幂次整除于2然后再多乘一次底数

对于以上涉及到 [判断奇偶性] 和 [除以2] 这样的操作。使用系统的位运算比普通运算的效率是高的，因此可以进一步优化：

• 把 power % 2 == 1 变为 (power & 1) == 1

• 把 power = power / 2 变为 power = power >> 1

class Solution {
public:
    double myPow(double x, int n) 
    {
        //将正数n和负数n都给转换为正数n
        //注意：int32 变量n∈[−2147483648,2147483647]
        //因此当 n = -2147483648 时执行 n = -n 会因越界而赋值出错
        //我们此处一开始就把 n 用 long long 存储
        long long b = n;
        if (n < 0) 
        {
            b = -b;
            x = 1 / x;
        }
        return culc(x, b);
    }

    //快速幂模版
    //递归的进行x的n次方计算
    double culc(double base, long power) 
    {
        double res = 1.0;
        while (power > 0) 
        {
            //两种情况会进入if语句：
            //1.幂次若为奇数，提前多乘一次x
            //2.当幂次除到1，把x赋值给res
            if ((power & 1) == 1)  //奇数
            {
                res *= base;
            }
            //幂次除以2
            power = power >> 1;
            //底数平方
            base = base * base;
        }
        return res;
    }
};

class Solution {
public:
    double myPow(double x, int n) 
    {
        //将正数n和负数n都给转换为正数n
        //注意：int32 变量n∈[−2147483648,2147483647]
        //因此当 n = -2147483648 时执行 n = -n 会因越界而赋值出错
        //我们此处一开始就把 n 用 long long 存储
        long long b = n;
        if (n < 0) 
        {
            b = -b;
            x = 1 / x;
        }
        return culc(x, b);
    }

    //递归
    double culc(double base, long power) 
    {
        if (power == 0)  return 1;
        double t = culc(base, power >> 1);
        if ((power & 1) == 1) return t * t * base;
        return t * t;
    }
};

class Solution {
public:
    double myPow(double x, int n) 
    {
       double res = 1.0;
       long long b = n; //防止溢出
       if(b < 0)
       {
           x = 1/x;
           b = -b;
       }  
       while(b > 0)
       {
           if(b&1) res *= x;
           x *= x;
           b >>= 1;
       }
       return res;
    }
};