剑指offer-16

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

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例

输入：x = 2.00000, n = 10
输出：1024.00000

输入：x = 2.10000, n = 3
输出：9.26100

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

解法

解法一：暴力法

超时

解法二：快速幂

快速幂解析（二进制角度）：

利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。

- 对于任何十进制正整数 $n$，设其二进制位 $ b _ { m } \ldots b_3 b_2 b _ { 1 }$（$b_i$为二进制某位值，$i\in [1,m]$），则有：
  - **二进制转十进制：** $1 b _ { 1 } + 2 b _ { 2 } + 4 b 3 + \ldots + 2 ^ { m - 1 } b _ { m }$ （既二进制转十进制公式）
  - **幂的二进制展开：**$x ^ { n } = x ^ { 1 b 1 + 2 b 2 + 4 b 3 + \ldots + 2 ^ { m - 1 } b m } = x ^ { 1 b 1 } x ^ { 2 b 2 } x ^ { 4 b 3 } \ldots x ^ { 2 ^ { m - 1 } b _ { m } }$；
- 根据以上推导，可把计算$x ^ { n }$转化为解决以下两个问题：
  - **计算** $x ^ { 1 } , x ^ { 2 } , x ^ { 4 } , \ldots , x ^ {{ 2 } ^ { m - 1 }}$**的值：** 循环赋值操作$x = x ^ { 2 }$即可；
  - **获取二进制各位 **$b _ { 1 } , b 2 , b 3 , \ldots , b _ { m }$，**的值：** 循环执行以下操作即可。
    1. $n \& 1$**（与操作）：** 判断 $n$ 二进制最右一位是否为  $1$；
    2. $n > > 1$ （移位操作）：  n 右移一位（可理解为删除最后一位）。
- 因此，应用以上操作，可在循环中依次计算$x ^ { 2 ^ { 0 } b 1 } , x ^ { 2 ^ { 1 } b 2 } , \ldots , x ^ { 2 ^ { m - 1 } b m }$ 的值，并将所有$ { x } ^{2 ^ { i - 1 } b _ { i }}$累计相乘即可。
  - 当 $b_i=0$时：$x ^ {{ 2 } ^ { i - 1 } b _ { i }} = 1$
  - 当$b_i=1$时：$x ^{ { 2 } ^ { i - 1 } b i }= x ^ {{ 2 } ^ { i - 1 }}$

快速幂解析（二分法角度）：

• 二分推导：$x ^ { n } = x ^ { n / 2 } \times x ^ { n / 2 } = \left( x ^ { 2 } \right) ^ { n / 2 }$,令$n/2$为整数，则需要分为奇偶两种情况（设向下取整除法符号为 “//“ ）：

  • 当 $n$ 为偶数：$x ^ { n } = \left( x ^ { 2 } \right) ^ { n / / 2 }$
  • 当 $n$ 为奇数：$x ^ { n } = x \left( x ^ { 2 } \right) ^ { n / / 2 }$，既会多出一项 $x$；

• 幂结果获取：

  • 根据二分推导，可通过循环 $x = x ^ { 2 }$ 操作，每次把幂从 $n$降至 $n//2$，直至幂降为0；

  • 设 $res=1$，则初始状态 $x^n = x^n \times res$。在循环二分时，每当 $n$ 为奇数时，将多出的一项 $x$ 乘入 $res$ ，则最终可化至 $x ^ { n } = x ^ { 0 } \times r e s = r e s$，返回 $res$ 即可。

    循环	$x^n$	res
    1.	$3^5$	1
    2.	$9^2$	1,3
    3.	$81^1$	1,3
    4.	$6561^0$	1,3,81

• 转为位运算：

  • 向下整除 $n//2$，等价于右移一位 $n>>1$；
  • 取余数 $n%2$，等价于判断二进制最后一位 $n&1$；

算法流程：

1. 当 $x=0$ 时：直接返回$0$（避免后续$x=\frac{1}{x}$操作报错）。
2. 初始化 $res=1$；
3. 当 $n<0$时：把问题转化至 $n \geq 0$ 的范围内，既执行 $x=\frac{1}{x}, n=-n$；
4. 循环计算：当$n=0$时退出；
   1. 当 $n&1=1$时：将当前 $x$ 乘入 $res$ （既 $res *= x$）；
   2. 执行 $x=x^2$（既$x*=x$）；
   3. 执行 $n$ 右移一位（既 $n>>=1$）。
5. 返回$res$。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0:
            return 0
        
        res = 1
        if n < 0:
            x = 1 /x
            n = -1 * n
        
        while n:
            # 判断是奇次幂还是偶次幂
            if n & 1 == 1: 
                res *= x
            x = x*x
            n >>= 1
        return res