class Solution {
public:
    double pow(double x, int n) {
        bool negative = false;
        if(n<0){
            negative=true;
            n=-n;
        }

        double res=1;
        while(n>0){
            if(n&1==1){
                res*=x;
                n--;
            }
            x*=x;
            n >>=1;
        }
        return negative? 1/res : res;
    }
};