当前位置: 首页 > article >正文

快速幂算法——求解大指数幂

定义+适用范围

快速幂算法(Fast Exponentiation)是一种高效的计算幂的方法,特别适用于计算形如 a^b的表达式,其中 a 是底数,b 是指数,且 b 可能非常大。

核心思想

快速幂算法的核心思想是将指数 b 表示为二进制形式,并利用二进制数的性质来减少乘法操作的次数。

基本思想

  1. 将指数 b 转换为二进制表示:例如,如果 b=13,则其二进制表示为 1101(2)​。

  2. 从右到左遍历二进制数的每一位:对于 b=13(10)​=1101(2)​,我们从右到左遍历每一位(即 1,0,1,1)。

  3. 根据当前位是 0 还是 1 来决定是否将当前的底数的幂乘到结果中

    • 如果当前位是 1,则将当前的底数的幂乘到结果中。
    • 如果当前位是 0,则不乘。
  4. 底数的幂每次循环都平方:在每次循环中,我们都将底数的当前幂平方,以便在下一次循环中使用。

  5. 指数每次循环都右移一位:这相当于将指数除以 2(在二进制表示中)。

示例

假设我们要计算 2^13。

  1. 13(10)​=1101(2)​
  2. 初始化 result = 1base = 2(result为结果,base为底数)
  3. 遍历 1101(2)​ 的每一位:
    • 最低位是 1,result *= base^1(即 result *= 2),然后 base = base^2(即 base = 4),指数右移一位(现在考虑 110(2)​)
    • 下一位是 0,不乘,base = base^2(即 base = 16),指数右移一位(现在考虑 11(2)​)
    • 下一位是 1,result *= base^1(即 result *= 16),然后 base = base^2(即 base = 256),指数右移一位(现在考虑 1(2)​)
    • 最高位是 1,result *= base^1(即 result *= 256

最终,result = 2 * 4 * 16 * 256 = 8192,即 2^13=8192。

代码实现

public double myPow(double x, int n) {  
    long N = n; // 使用 long 防止溢出  
    if (N == 0) return 1.0;  
      
    boolean isNegative = N < 0;  
    N = Math.abs(N);  
      
    double result = 1.0;  
    double base = x;  
      
    while (N > 0) {  
        if ((N & 1) == 1) { // 如果 N 的当前最低位是 1  
            result *= base;  
        }  
        base *= base; // base 平方  
        N >>= 1; // N 右移一位(相当于除以 2)  
    }  
      
    if (isNegative) {  
        result = 1.0 / result;  
    }  
      
    return result;  
}


http://www.kler.cn/a/290917.html

相关文章:

  • 法学硕士,有哪些专业可以申请呢?
  • scala基础学习(数据类型)-字符串
  • GTID详解
  • Jenkins持续集成部署——jenkins安装
  • springboot463学生信息管理系统论文(论文+源码)_kaic
  • ElasticSearch08-分析器详解
  • 咖啡与开源访谈 -- Ian Taylor
  • onvif应用--IPC鉴权(认证)
  • 数学基础 -- 微积分之数列与级数
  • AI学习指南深度学习篇-SGD的变种算法
  • Linux【6】系统
  • leetcode 94.二叉树的中序遍历
  • JS中数组的方法flat()怎么用
  • 使用Spring Cloud Consul进行分布式配置的深度解析与实战
  • 使用vscode编辑matlab完美解决方法
  • Python Magic Method 与 Setup 方法:深入解析与应用
  • 【C++】类和对象(三)再探构造函数|static成员函数|友元函数|内部类|匿名对象|对象拷贝时的编译优化
  • 新一代交互模式:LUICUIVUI
  • 基于web旅游信息平台的设计与实现
  • MATLAB实现跳频多频移键控通信系统仿真
  • 记录Jmeter 通过view result tree配置保存响应信息的方法以及命令行运行时的一个坑
  • C++中protobuffer的具体使用方法以及重要原理的实现
  • 尚硅谷前端 ES6 笔记
  • 网恋照妖镜源码搭建教程
  • Java IO异常处理:在Web爬虫开发中的实践
  • element-ui单元格点击后进入编辑模式的功能