剑指Offer-快速幂

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0

解法

1. 暴力法

思路：使用循环进行累乘，多少次方就循环多少次。（注意exponent可能为负数的情况！）

public class Solution {
  public double Power(double base, int exponent) {
    if (base == 0) return 0;
    double result = 1.0f;
    // exponent负数情况
    if (exponent < 0) {
      exponent = -exponent;
      base = 1 / base;
    }
    for (int i = 0; i < exponent; i++) {
      result *= base;
    }
    return result;
  }
}

时间复杂度为$O(n)$，空间复杂度为$O(1)$

2. 快速幂

上面的暴力法时间复杂度是$O(n)$，看起来挺好，但当exponent特别大时，性能就变得很低了。而快速幂算法可以将时间复杂度降为$O(logn)$，十分优秀👍。

快速幂：快速求出幂指数的一种算法。思路是将指数换算为二进制数，根据权重（当前位是否为1）来考虑是否乘当前位的数值。

例如计算$3^9$

暴力法：$1333…33*3$ 需要乘9个3，即乘9次。

快速幂：将9换算为二进制数为1001
$3^9 = 3^{(2^31 + 2^20 + 2^10 + 2^01)} = 3^{2^31}3^{(2^0*1)}$ 可以看到转换为二进制后，只需要乘4次。

接下来用代码实现

public class Solution {
  public double Power(double base, int exponent) {
    if (base == 0) return 0;
    double result = 1;
    if (exponent < 0) {
      exponent = -exponent;
      base = 1 / base;
    }
    // 初始化基底（即base^(2^0)）
    double a = base;
    // exponent为0时，停止循环
    while (exponent != 0) {
      // 使用&操作判断exponent的二进制数最后一位是否为1
      if ((exponent & 1) == 1) {
        // 此时说明权重为1，应乘上基底
        result *= a;
      }
      // 将exponent二进制右移一位，准备检查下一位是否为1
      exponent = exponent >> 1;
      // 更新基底
      a = a * a;
    }
    return result;
  }
}