二分快速幂

二分快速幂

该算法用来计算a的b次方，通过将指数化为2的进制表示法，来降低乘法的运算次数，比如a的9次方，因为9 = 1001(二进制),所以可以写成a^9 = a^(2^0)*a^(2^3);这样可以将算法复杂度由o(n)将为o(logn).

public class Solution {
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        boolean flag = true;
        if (exponent < 0) {
            exponent = -exponent;
            flag = false;
        }
        double res = 1;
        while (exponent != 0) {
            if ((exponent & 1) == 1) {
                res *= base;
            }
            base *= base;
            exponent = exponent >> 1;
        }
        if (flag == false) {
            return (1 / res);
        } 
        return res;
  }
}