作者：小傅哥
博客：https://bugstack.cn - 包含: JAVA 基础，面经手册.NETty4.x，手写Spring，用Java实现JVM，重学Java设计模式，SpringBoot中间件开发，IDEA插件开发，DDD系统架构项目开发，字节码编程...
沉淀、分享、成长，让自己和他人都能有所收获！一、前言
不知道读者伙伴用了那么久的 Java Math 函数，是否有打开它的源码，看看是如何实现的。比如 Math.pow 函数计算数字的次方值，只要你打开它的源码，你会惊讶到；这在弄啥，这都是啥，这要干啥！
这是啥，这就是一段用于计算次方的算法。简单来说，它是通过在 Math.pow 中预先构建了一个基于查表的算法，保存了常用的幂的值，然后使用这些值来快速计算幂次方。
其实用于计算次幂的方法还有很多，包括；递归、滑动窗口（Sliding-window method）、蒙哥马利的梯子技术（Montgomery's ladder technique）、固定底数（Fixed-base exponent）等方式来计算。接下来小傅哥就给大家分享下这些算法方案。
二、算法实现
其实无论是那样一种计算次幂的方式，都离不开核心的基础模型。也就是说，任何一个数的次幂，都是这个次幂下数字的乘积累计值。包括使用递归、还是通过二进制数字移位，最终都要归到幂的乘积。
public static double pow01(double base, double power) { if (power == 0) { return 1; } if (power % 2 == 0) { double multiplier = pow01(base, power / 2); return multiplier * multiplier; } double multiplier = pow01(base, Math.floor(power / 2)); return multiplier * multiplier * base; }
public static long pow03(int base, int exponent) { if (exponent == 0) { return 1; } if (exponent == 1) { return base; } long result = 1; long window = base; while (exponent > 0) { if ((exponent & 1) == 1) { result *= window; } window *= window; exponent >>= 1; } return result; }
public static BigInteger pow04(BigInteger x, BigInteger n) { BigInteger x1 = x; BigInteger x2 = x.multiply(x); for (int i = n.bitLength() - 2; i >= 0; i--) { if (n.TestBit(i)) { x1 = x1.multiply(x2); x2 = x2.multiply(x2); } else { x2 = x1.multiply(x2); x1 = x1.multiply(x1); } } return x1; }
public static BigInteger pow05(BigInteger base, BigInteger exponent) { int e = exponent.intValue(); BigInteger result = BigInteger.ONE; BigInteger current = base; while (e > 0) { if ((e & 1) == 1) { result = result.multiply(current); } current = current.multiply(current); e >>= 1; } return result; }
@Test public void test_FastPowering() { System.out.println("测试结果：" + FastPowering.pow01(2, 4)); System.out.println("测试结果：" + FastPowering.pow02(2, 10)); System.out.println("测试结果：" + FastPowering.pow03(2, 4)); System.out.println("测试结果：" + FastPowering.pow04(BigInteger.valueOf(2), BigInteger.valueOf(10))); System.out.println("测试结果：" + FastPowering.pow05(BigInteger.valueOf(2), BigInteger.valueOf(10))); }
测试结果
测试结果：16.0 测试结果：1024 测试结果：16 测试结果：1024 测试结果：1024 Process finished with exit code 0
京公网安备 11010802035086号