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

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。


示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：

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

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

提示：

-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104

思路

累乘的思路，典型的快速幂思路。如果逐个累乘，需要for循环n次，但是如果用快速幂（二分），则可以在n^(1/2)^内完成。

例如：

如果求2^10^，在正常思路下，我们需要2*2*2*2*2*2*2*2*2*2，这样乘10次，但是如果我们使用二次幂的思想：我们可以用10^(1/2)^=4次循环完成

1
2
3
4
5
第一次：a = 2 * 2
第二次：b = a * a  //4 * 4
第三次：c = b * b  //16 * 16
第四次：c = c * c  //256 * 256

所以接下来完成具体过程：

注意1：在奇数幂和偶数幂的情况下不一样
$$
当 nn 为偶数： x^n = (x^2)^{n/2}
\当 nn 为奇数： x^n = x(x^2)^{n/2},会多出来一项x
$$
注意2：在幂可以为负数

如果幂为负数，我们可以转换为乘以(1/x) ，然后把幂的次数还是转化为正数

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static class Solution {
    public double myPow(double x, int n) {
        // 如果x为0，直接返回
        if (x == 0) {
            return 0;
        }
        long b = n;
        double res = 1.0;
        // 如果幂为负数，转化为乘以1/x，然后还是把幂转为正数
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        // 利用二分法，只有当幂的值大于零的时候乘
        while (b > 0) {
            // 如果幂为奇数，需要多乘一步，因为奇数除以2后，后四舍
            // b & 1，判断一个数是偶数还是奇数，如果是奇数二进制最后一位必然为1
            if ((b & 1) == 1) {
                // 如果是奇数，乘以x的值，因为最后当b=1的时候是最后一次，这个时候我们res及时最后的结果了
                // 如果不在这里乘积，也可以写在别的的位置，就是在写一个if判断
                res *= x;
            }
            x *= x;
            b >>= 1;
        }

        return res;
    }
}