幂的运算：X的n次幂
2024-10-19 04:33:28
计算X的n次幂，有多种算法
例子：计算2的62次方。
method 1 ：time = 1527 纳秒。
常规思路，进行61次的乘法！
private static long mi(long X, long n) {
long start = System.nanoTime();
long result = 1;
for (long k = 0; k < n; k++) {
result *= X;
}
System.out.println(System.nanoTime()-start);
return result;
}
method 2 ：time = 113 纳秒
进行拆分：2^62 = (2^31)^2 = (2^31)*(2^31) // 得到 2^31 的值的情况下，需要 1 次乘法
2^31 = (2^15)^2*2 = (2^15)*(2^15)*2 // 得到 2^15 的值的情况下，需要 2 次乘法
2^15 = (2^7)^2*2 = (2^7)*(2^7)*2 // 得到 2^7 的值的情况下，需要 2 次乘法
2^7 = (2^3)^2*2 = (2^3)*(2^3)*2 // 得到2^3 的值的情况下，需要 2 次乘法
2^3 = 2*2*2 // …………………………，需要2次乘法
所以：该方法需 2+2+2+2+1 = 9 次乘法！
/**
* 求x的n次方的值。
* 幂函数：
* x的n次幂
* @param x
* @param n
* @return
*/
public static long pow(long x, long n) { long start = System.nanoTime();
if (n == 0) {
System.out.println(System.nanoTime()-start);
return 1;
}
// 如果是偶数
if (isEven(n)) {
return pow(x * x, n / 2);
} else {
return pow(x * x, n / 2) * x;
}
} /**
* 判断x是否是偶数
*
* @param x
* @return
*/
private static Boolean isEven(long x) {
if (x % 2 == 0) {
return true;
}
if (x % 2 == 1) {
return false;
}
return false;
}
最新文章
- thinkphp 3.2.3 动态修改conf配置文件
- Android异步消息处理机制完全解析，带你从源码的角度彻底理解（转）
- AutofacContainer
- Java实现文件复制的四种方式
- MVC_表单和HTML辅助方法
- DropDownList中显示无限级树形结构
- Android编码风格
- linux 软件安装各种方法
- Request To JavaBean(请求对象转换为JavaBean对象)
- Linux下glui 的安装,以及错误解决
- Counting - SGU 117（快速幂）
- Java基础知识强化之IO流笔记16：IO流的概述和分类
- AutoIt 函数学习之----WinWaitActive
- 使用 C# 进行 Outlook 2003 编程
- cefsharp实现javascript回调C#方法
- jQuery中jsonp函数实现
- C++ Primer 有感（复制控制）
- 认识容器和Docker（一）
- 常用js正则表达式大全
- WPS for Linux