非递归快速幂（求一个数的n次幂）

/*
时间复杂度为logn   
b^{9}=b*((b^2)^2)^2)   
递归思路：
当n&1不为0时; f(b,n)=f(b,n/2)*b  为奇数时。
当n&1为0时;  f(b,n)=f(b,n/2)    为偶数时。
*/
class Solution {
public:

    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }//负数次方归正
        double x = b; // 记录x^0, x^1, x^2 ...
        double ret = 1.0;
        while (n) {
            if (n&1) {
                ret *= x; // 二进制位数是1的，乘进答案。
            }
            x *= x;
            n >>= 1;
        }
        return ret;
    }
};