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

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

• 解题思路
• 代码

解题思路

这题用快速幂 来解决。
重点：快速幂计算x^n 时，把n看成二进制数。

举例：

状态    遍历位    n      base  res
初始化    --    1010     2      1
第一次    0     (0)101   2^2    1
第二次    1     (00)10   2^4    1 * 2^2
第三次    0     (000)1   2^8    1 * 2^2
第四次    1     (0000)   2^10   1 * 2^2 * 2^8   
第五次    n为0结束

注意：只有二进制位为1的时候才需要更新res，因为2^0=1，1*res=res

代码

class Solution {
    public double myPow(double x, int n) {
        if (x == 0) {
            return 0;
        }
// 变量 n∈[−2147483648,2147483647] ，因此当 n = -2147483648n=−2147483648 时执行 n = -n会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。
        long b = n;
        double res = 1.0;

        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b > 0) {
            //二进制最右边数的是1
            if ((b & 1) == 1) {
                res = res * x;
            }
            x *= x;//基底翻倍
            b = b >> 1;//右移b1位，其实就是删除最后那个二进制数
        }
        return res;
    }
}