剑指offer_发散思维---数值的整数次方-阿里云开发者社区

剑指offer_发散思维---数值的整数次方

2023-06-17 71

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 剑指offer_发散思维---数值的整数次方

##题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

##解题思路

主要涉及完整性考虑，首先按照正数次幂，负数次幂，0次幂，三种分析，底数为0和非0。

1，第一种方式，常规做法

2，第二种方式，用递归的方法，效率提高

3，第三种方式，用快速幂的方法，可以实现递归的效果

##代码实现

/**
 * 
 */
package 发散思维;
/**
 * <p>
 * Title:Power
 * </p>
 * <p>
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月25日 上午9:49:35
 */
public class Power {
  /**
   * void
   * 
   * @param args
   */
  public static void main(String[] args) {
    System.out.println(DouPowerSuperMax(-2.0, -3));
  }
  // ==================================================================常规方法
  public static double DouPower(double base, int exponent) {
    if (base == 0) {
      return 0;
    }
    if (exponent > 0) { // 正数次幂
      double result = 1;
      for (int i = 1; i <= exponent; i++) {
        result *= base;
      }
      System.out.println(result);
      return result;
    } else if (exponent < 0) {
      double result = 1;
      for (int i = 1; i <= -exponent; i++) { // 负数次幂
        result *= base;
      }
      return 1 / result;
    } else { // 任何数的0次幂都是1
      return 1;
    }
  }
  // ==================================================================递归方式
  public static double DouPowerSuper(double base, int exponent) {
    if (exponent > 0) {
      return helper(base, exponent);
    } else {
      return 1.0 / helper(base, exponent);
    }
  }
  public static double helper(double base, int exponent) {
    if (exponent < 0) {
      exponent = -exponent;
    }
    if (exponent == 0) {
      return 1;
    }
    if (exponent == 1) {
      return base;
    }
    double result = helper(base, exponent >> 1); // 递归方式可以让指数成倍的增长，减少运算次数
    result *= result;
    if ((exponent & 1) == 1) {
      result *= base; // 如果是奇数，要多乘一次
    }
    return result;
  }
  // ==================================================================快速幂方式
/**
 * 1.全面考察指数的正负、底数是否为零等情况。
 * 2.写出指数的二进制表达，例如13表达为二进制1101。
 * 3.举例:10^1101 = 10^0001*10^0100*10^1000。
 * 4.通过&1和>>1来逐位读取1101，为1时将该位代表的乘数累乘到最终结果。
 */
  public static double DouPowerSuperMax(double base, int exponent) {
    int flag = exponent;
    if (base == 0)
      return 0;
    if (exponent == 0) {
      return 1;
    }
    if (exponent < 0) {
      exponent = -exponent;
    }
    int res = 1;
    while (exponent != 0) {
      if ((exponent & 1) != 0) {
        res *= base;
      }
      base *= base;
      exponent = exponent >> 1;
    }
    return flag > 0 ? res : 1.0 / res;
  }
}