LeetCode OJ:Pow(x, n)

1471 단어 LeetCode

Pow(x, n)

 
Implement pow(x, n).
알고리즘:
TLE 반환,
이분법:
class Solution {
public:
    double pow(double x, int n) {
        if(n==0)return 1.0;
        if(n<0){
            if(n==INT_MIN)return 1.0/(pow(x,INT_MAX)*x);
            return 1.0/pow(x,-n);
        }
        double mid = pow(x,n>>1);  
        return n%2?mid*mid*x:mid*mid;
    }
};

Consider the binary representation of n. For example, if it is "10001011", then x^n = x^(1+2+8+128) = x^1 * x^2 * x^8 * x^128. Thus, we don't want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1 << i) to the result. Since (1 << i) is a power of 2, x^(1<<(i+1)) = square(x^(1<class Solution { public: double pow(double x, int n) { if(n==0) return 1.0; if(n<0) { if(n==INT_MIN) return 1.0 / (pow(x,INT_MAX)*x); return 1.0 / pow(x,-n); } double ans = 1.0 ; for(;n>0; x *= x, n>>=1) { if(n&1) ans *= x; } return ans; } };

좋은 웹페이지 즐겨찾기