题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
分析
看似简单，需要注意的小细节比较多！！首先要充分考虑好边界条件，还要考虑到如果指数exponent为负数的情况。
解法1（传统解法，时间复杂度为O(n)）
public class Solution { public double Power(double base, int exponent) { if (base ==0.0 && exponent <= 0) throw new RuntimeException(); if (exponent == 0) return 1; if (base == 0) return 0; int absExponent = exponent > 0 ? exponent : -exponent; double result = 1.0; for(int i = 0; i < absExponent; i++) result *= base; return exponent > 0 ? result : 1.0/result; } }
解法2（快速幂算法，时间复杂度为O(logn)）
快速幂求a的n次方：
另外，应尽可能用位运算代替乘除法以及求余运算，因为位运算的效率要高得多！！比如，可以用右移代替除以2，用位运算符代替求余运算符%来判断一个数是的奇偶性。
☆解法2.1 快速幂的递归实现
public class Solution { public double Power(double base, int exponent) { if (base ==0.0 && exponent <= 0) throw new RuntimeException(); if (exponent == 0) return 1; if (base == 0) return 0; int absExponent = exponent > 0 ? exponent : -exponent; double result = PowWithUnsignedExponent(base, absExponent); return exponent > 0 ? result : 1.0/result; } //快速幂算法的递归实现 public double PowWithUnsignedExponent(double base,int absExponent){ if (absExponent == 0) return 1; if (absExponent == 1) return base; double result = PowWithUnsignedExponent(base,absExponent>>1);// 口诀：左移乘2，右移除2 result *= result; //位运算判断奇偶性，如果为0即为偶数，反之为1即为奇数 if ((absExponent & 1)==1) result *= base; return result; } }
解法2.2 快速幂非递归实现，递推
public class Solution { public double Power(double base, int exponent) { if (base ==0.0 && exponent <= 0) throw new RuntimeException(); if (exponent == 0) return 1; if (base == 0) return 0; int absExponent = exponent > 0 ? exponent : -exponent; double result = 1.0; while(absExponent > 0){ if((absExponent & 1) == 1) result *= base; absExponent = absExponent >> 1; base *= base; } return exponent > 0 ? result : 1.0/result; } }