问题

剑指 Offer 16. 数值的整数次方
难度中等53
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2 = 1/2 = 1/4 = 0.25
说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−2, 2− 1] 。

解答

image.png

int 越界问题： n 的取值范围为 [ -2, 2- 1] 这个区间中。当 n 为 -2 时，将 n 转为正数，则会出现数据越界问题，所以利用一个 long 型来存储。

算法的执行流程：以 n = 1001（9）为例， 其二进制转十进制为
image.png
首先判断 n 是否为负数，如果为负数，则 x = 1/x
while 循环 ：

  • 判断 exponent 是否为奇数，如果为 (exponent & 1) == 1，说明其二进制位中的数是有效的，将其乘入 res 中，例如 1001 中，有效位为 2 和 2，将其乘入 res 中，0 位则不乘入 res 中，如 2和 2
  • x 自身相乘
  • exponent 向下整除 2
    1. class Solution {
    2.   public double myPow(double x, int n) {
    3.       long exponent = n;
    4.       double res = 1.0;
    5.       // n 为负数的情况
    6.       if (exponent < 0){
    7.           x =  1 / x;
    8.           exponent = -exponent;
    9.       }
    10.       // 快速幂等
    11.       while(exponent > 0){
    12.           if ((exponent & 1) != 0){
    13.               res *=  x;
    14.           }
    15.           x *= x ;
    16.           exponent >>= 1; 
    17.       }
    18.       return res;
    19.   }
    20. }

大佬的解题思路总结：
https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/solution/mian-shi-ti-16-shu-zhi-de-zheng-shu-ci-fang-kuai-s/