My answer using bit operation (C++ implementation)


  • 16
    M
    class Solution {
    public:
        double pow(double x, int n) {
        	if(n<0){
        		x = 1.0/x;
        		n = -n;
        	}
        	int unsigned m = n;
            double tbl[32] = {0};
            double result = 1;
            tbl[0] = x;
            for(int i=1;i<32;i++){
                tbl[i] = tbl[i-1]*tbl[i-1];
            }
            for(int i=0;i<32;i++){
                if( m & (0x1<<i) )
                result *= tbl[i];
            }
            return result;
        }
    };
    

    In bit format and for a unsigned number, the number is represented as k0*2^0 + k1*2^1 + ... +k31*2^31. Therefore, once we know the pow(x,2^0), pow(x,2^1), ..., pow(x,2^31), we can get pow(x,n). And pow(x,2^m) can be constructed easily as pow(x,2^m) = pow(x,2^(m-1)*pow(x,2^(m-1).


  • 0
    J

    Interesting solution, but I think it uses too much extra space...


  • 0
    K

    how long is the running time?


  • 0
    T

    I used similar method, my C++ code costed 40ms.
    Just one thing, in the second for statement, 32 should be 31, since the (1<<31) bit is sign bit.


  • 0
    M

    True and good suggestion. Though the 32 bit of n should always be zero as I turned n into a positive number.


  • 0
    S

    Its 4ms when I run it. Same as std::pow.


  • 0
    B

    is this o(1) time cost?


  • 0
    N

    cool solution, you can save more by putting them into one loop and stop when no further "1"s in n

    double myPow(double x, int n) {
        if(n<0){
            x = 1.0/x;
        	n = -n;
        }
        
        double tbl[32] = {x};
        unsigned int n_tmp = n;
        double ret = (n_tmp & 1UL)?tbl[0]:1;
        
        for(int i = 1; (1UL<< i) <= n_tmp; i++){
            tbl[i] = tbl[i-1] * tbl[i-1];
            ret *= (n_tmp & (1UL << i))?tbl[i]:1;
        }
        return ret;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.