剑指Offer小解析——16.数值的整数次幂（从二分角度去理解）
作为一个资深的抄题家，每次做题都是自己想出来的少，看别人的答案多。当做到16题的时候，我去看解析，看到了Krahets大佬的解答–>解析点击这里，他对快速幂的两种角度的分析十分透彻，但是第二种，二分角度的分析我还是不太明白，后来用了一天的时间想通了以后，特此记录一下。
首先我们要记住一个公式
{ x n = x n 2 × x n 2 ( n 为 偶 数 ) x n = x n − 1 2 × x n − 1 2 × x ( n 为 奇 数 ) \left\{ \begin{aligned} x^{n} = x^{\frac{n}{2}} \times x^{\frac{n}{2}} (n为偶数)\\ x^{n} = x^{\frac{n - 1}{2}} \times x^{\frac{n - 1}{2}} \times x (n为奇数) \end{aligned} \right. { xn=x2n×x2n(n为偶数)xn=x2n−1×x2n−1×x(n为奇数)
首先粘贴代码
public static double myPow(double x, int n) {
double temp = 1;
double result = 1;
long b = Math.abs(n);
if (b < 0) {
b = -b;
}
if (n == 0) {
return 1;
} else {
while(b > 0) {
if ((b & 1) == 1) {
result *= x;
}
x *= x;
b >>= 1;
}
return n > 0 ? result : temp / result;
}
}
这里我们以3的9次方为例，设res等于1。
3 9 = ( 3 4 ) 2 × 3 × r e s 3^{9} = (3^{4})^{2} \times 3 \times res 39=(34)2×3×res
= ( ( 3 2 ) 2 ) 2 × 3 × r e s = ((3^{2})^{2})^{2} \times 3 \times res =((32)2)2×3×res
= ( ( ( 3 1 ) 2 ) 2 ) 2 × 3 × r e s = (((3^{1})^{2})^{2})^{2} \times 3 \times res =(((31)2)2)2×3×res
= ( ( ( 3 0 × 3 ) 2 ) 2 ) 2 × 3 × r e s = (((3^{0} \times 3)^{2})^{2})^{2} \times 3 \times res =(((30×3)2)2)2×3×res
= ( ( ( 3 0 ) 2 ) 2 ) 2 × ( ( ( 3 ) 2 ) 2 ) 2 × 3 × r e s = (((3^{0})^{2})^{2})^{2} \times (((3)^{2})^{2})^{2} \times 3 \times res =(((30)2)2)2×(((3)2)2)2×3×res
= ( ( ( 3 0 ) 2 ) 2 ) 2 × 3 8 × 3 × r e s = (((3^{0})^{2})^{2})^{2} \times 3^{8} \times 3 \times res =(((30)2)2)2×38×3×res
= 3 8 × 3 × r e s =3^{8} \times 3 \times res =38×3×res
其实这个过程就代表着下面这个循环的流程
int res = 1
while(b > 0) {
if ((b & 1) == 1) {
res *= x;
}
x *= x;
b >>= 1;
}
3 9 = ( 3 4 ) 2 × 3 × r e s 3^{9} = (3^{4})^{2} \times 3 \times res 39=(34)2×3×res (b = 9, x = 3^1)
= ( ( 3 2 ) 2 ) 2 × 3 × r e s = ((3^{2})^{2})^{2} \times 3 \times res =((32)2)2×3×res (b = 4, x = 3^2 = 9)
= ( ( ( 3 1 ) 2 ) 2 ) 2 × 3 × r e s = (((3^{1})^{2})^{2})^{2} \times 3 \times res =(((31)2)2)2×3×res (b = 2, x = 3^4 = 9^2 = 81)
= ( ( ( 3 0 ) 2 ) 2 ) 2 × 3 8 × 3 × r e s = (((3^{0})^{2})^{2})^{2} \times 3^{8} \times 3 \times res =(((30)2)2)2×38×3×res (b = 1, x = 3^8 = 81^2 = 6561)
= 3 8 × 3 × r e s =3^{8} \times 3 \times res =38×3×res
每次循环，我们都将x平方；
为什么？看上面的连等，当b也就是指数为9的时候，我们可以把其化成 ( 3 4 ) 2 × 3 (3^{4})^{2} \times 3 (34)2×3 ，
那么我们可以继续化，直接将 ( 3 4 ) 2 (3^{4})^{2} (34)2化成 ( ( 3 2 ) 2 ) 2 ((3^{2})^{2})^{2} ((32)2)2
……
在每次循环中，x都起到一个记录的作用，记录的是啥呢？如果你看懂上面的过程了，就会知道，x记录的是如果括号内的3脱离括号后的最终结果。这么说太抽象，就像下面这个过程
= ( ( ( 3 1 ) 2 ) 2 ) 2 × 3 × r e s = (((3^{1})^{2})^{2})^{2} \times 3 \times res =(((31)2)2)2×3×res
= ( ( ( 3 0 × 3 ) 2 ) 2 ) 2 × 3 × r e s = (((3^{0} \times 3)^{2})^{2})^{2} \times 3 \times res =(((30×3)2)2)2×3×res
= ( ( ( 3 0 ) 2 ) 2 ) 2 × ( ( ( 3 ) 2 ) 2 ) 2 × 3 × r e s = (((3^{0})^{2})^{2})^{2} \times (((3)^{2})^{2})^{2} \times 3 \times res =(((30)2)2)2×(((3)2)2)2×3×res
= ( ( ( 3 0 ) 2 ) 2 ) 2 × 3 8 × 3 × r e s = (((3^{0})^{2})^{2})^{2} \times 3^{8} \times 3 \times res =(((30)2)2)2×38×3×res
如果指数为奇数，说明我们可以提出一个3，比如把 3 1 3^1 31变成 3 0 × 3 3^0 \times 3 30×3
但是这个3要想和res结合，一定是要脱离括号的，一步一步向外脱离，每一次都平方一下，最后变成了 3 8 3^8 38，x就是负责每次循环都计算一下下一次如果指数是奇数，里面的一个3要脱离括号会变成几。如果循环时指数为奇数，我们就用res乘以x，如果是偶数，就不用管。
大致就是如此。
京公网安备 11010502036488号