剑指 Offer 16— 数值的整数次方

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

求 x^n 最简单的方法是通过循环将 n 个 x 乘起来，依次求 x^1、x^2、x^3.......，时间复杂为 O(n)

快速幂法 可将时间复杂度降低至 O(log n)。

比如要求x^11，正常的乘积需要循环乘11次，时间复杂度为O(n)。

快速幂的思想就是将指数11 可以转成二进制数1011，则原来的式子可以转化成：x^(2^3+2^1+2^0) = x^(1*2^3) * x^(0*2^2) * x^(1*2^1) * x^(1*2^0)

                            =  x^(8) * x^(2) *  x^(1)。

11的二进制是1011，只有在 1 的位置上，才有相应的权重，所以需要判断 (b&1)是否等于1判断最右边是否为1。

此时只运算了3次乘积，时间复杂度降至O(logn)。

class Solution {
public:
    double myPow(double x, int n) 
    {
       if(0==x)
       {
           return 0;
       }
       long b=n;//用long来接n，以防超出整数范围
       if(b<0)
       {
           x=1/x;
           b=(-b);
       }
       double res = 1.0;
       while(b>0)
       {
           if( (b&1)==1 )
           {
               // b的最右边为1，此时有权重
               res*=x;
           }
           x*=x; //x,x^2,x^4.....
           b=b/2;
       }

       return res;
    }
};