leetcode 50. Pow(x, n) 快速幂

地址：https://leetcode-cn.com/problems/powx-n/
实现Math.pow(n,x);

暴力是直接相乘，则需要进行n次。将n转为2进制，最多只需要logn次相乘，但需要获得每次的基数base。

转为2进制可能是基数好算一些?

java中int的极限，0-2147483648 = -2147483648，所以需要用long

class Solution {
    public double myPow(double x, int n) {
        double r = 0;
        long N = n;// !!!!!
        //while(n>1)
        if(n>0)
        r = f(x,n);
        else
        r = 1/ f(x,-N);
        return r;
    }

    private double f(double x,long n){
        double  r = 1;
        double s =x;
        while(n>0){
            if( (n&1) == 1){ // (n&1) 需要加括号
                r = r*s;
            }
            s = s *s;// 需要不断相乘，获得基数base
            n = n >>1;
        }
        return r;
    }
}