剑指 Offer 16. 数值的整数次方

二分法O(logn)

class Solution {
public:
    double myPow(double x, int n) {
        double ret = 1;
        long b = static_cast<long>(n);
        if(b < 0)
        {
            b = -b;   // 先反转成全是正数
            x = 1/x;  // 基准
        }
        while(b)
        {
            if(b & 1)
                ret *= x;  // 如果次数为奇数 那么先乘一个x, 如果结束前的一次迭代b = 2，那么会进入1，如果b = 1，那此时已经进入了，最后b=0时，因为0次方=1，所以没影响。
            x *= x; // 转为x^2
            b >>= 1; // 转为n/2
            // 操作过后 基准变为x^2，x^2成为了下一个x，而n/2成为了下一个n，由此迭代
        }
        return ret;
    }
};

当输入的次数n为奇数时

\[ X^n=X*(X^2)^{n/2}\]

当输入的次数n为偶数时

\[ X^n=(X^2)^{n/2}\]