050 - Pow(x, n)

Pow(x, n)

Implement pow(x, n).
Hide Tags
Math Binary Search
Hide Similar Problems
(M) Sqrt(x)

当然不是要求直接乘上n次。
提示说是binary search，其实也不算search，但确实是二分。
递归和迭代都写了，迭代稍微费点儿脑子。
递归：
    每次都n/2，最后肯定会得到0，这就是底了。
    然后按照n/2的值是奇数偶数，再依次算回来：
    偶数 = 平方；正奇数 = 平方* x；负奇数 = 平方/x；
迭代：
    肯定不能让nn=1然后每次乘2，那只能得到2,4,8,16…次方
    仔细想想，实际上关键就是要知道每一步指数折半之后是奇还是偶，
    而这个实际上就是具体每一个bit位嘛，所以把每个bit位都存下来，
    然后只要从最高位+1开始（相当于除2一直除到等于0），
    统计bit位的时候不带符号位，且要用绝对值，不然负数就是一堆 bit 1 了。
    依次按照bit位为 1 还是 0 来决定乘以 rst*x 还是 rst 就好了。
    最后如果n是负的，用1除一下就好。
相比递归，只有一次除法运算，空间是常量，时间复杂度一样。（跑出来都是 4 ms）

class Solution {
public:
    //recursive
    double myPow(double x, int n) {
        if(!n)
            return 1;
       
        double rst=myPow(x, n/2);
        rst *= (n%2)?(n>0?(rst*x):(rst/x)):rst;
        return rst;
    }

    //iterative
    double myPow(double x, int n) {
        double rst=1.0;
       
        if(n)
        {
            int nn=abs(n), count=0, bits[32]={0};
   
            while(nn && count<31){
                bits[count++]=(nn&1);
                nn=nn>>1;            }
   
            while(count>=0)
                rst *= (bits[count--])?(x*rst):rst;
        }
        return (n>=0)?rst:(1/rst);
    }
};
4 ms.