题目
https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
解题
移位等操作，边界条件
快速幂解析（二分法角度）：
快速幂实际上是二分思想的一种应用。
二分推导：$x^{n} = x^{n/2} * x^{n/2} = (x^{2})^{n/2}$, 令n/2为整数，则需分奇偶 两种情况
- 当n为偶数：$x^{n} = (x^{2})^{n/2}$;
- 当n为奇数：$x^{n}=x(x^{2})^{n/2}$, 即会多一项 x；
幂结果获取
- 根据二分推导，可以通过 循环 $x=x^{2}$ 每次吧幂从n将至n//2,直至将幂降为0。
- 设res=1,则初始状态 $x^{n} = x^{n} res$，在循环二分时，每当n为奇数，将会多出一项 x 乘入res，则最终可以退化为 $x^{n} = x^{0} res = res$, 返回res即可。
- 转为位运算:
- 向下整除 n/2 等价于 n >> 1
- 取余数 n%2 等价于 判断二进制最右一位的值 n&1
- 算法流程
- 当 x = 0时：直接返回 0 （避免后续$ x = 1 / x$操作报错）。
- 初始化 $res = 1$ ；
- 当$ n < 0$ 时：把问题转化至$ n \geq 0$ 的范围内，即执行$ x = 1/x$ ，$n = - n$ ；
- 循环计算：当 $n = 0$ 时跳出；
- 当 $n \& 1 = 1$ 时：将当前 $x$ 乘入$ res$ （即 $res *= x$ ）；
- 执行 $x = x^2$（即 x *= x ）；
- 执行 nn 右移一位（即 n >>= 1n>>=1）。
- 返回 res。
1 | class Solution { |