/* * 方式一:直接运算(注意负数转换正数之后运算) * step 1:先处理次方数为负数的情况,将底数化为分数解决。 * step 2:遍历次方数的次数,不断累乘底数。 * */ public double Power(double base, int exponent) { if(exponent < 0){ base = 1/base; exponent = -exponent; } double res = 1.0; // 累计乘数 for (int i = 0; i < exponent; i++) { res*=base; } return res; } /* * 方式二:快速幂(分治) * step 1:先处理次方数为负数的情况,将底数化为分数解决。 * step 2:使用快速幂计算次方:将已乘出来的部分求次方,可以每次缩小一半要求的次方数。 * */ public double Power2(double base, int exponent) { //处理负数次方 if(exponent < 0){ base = 1 / base; exponent = -exponent; } return Pow(base, exponent); } //快速幂 private double Pow(double x, int y){ double res = 1; while(y != 0){ //可以再往上乘一个,如果是奇数多乘一次 if((y & 1) != 0) res *= x; //叠加 x *= x; //减少乘次数 y = y >> 1; } return res; }
解题思想:注意负整数需要转换为正整数
方式一:乘法
方式二:快速幂(分治)