50. Pow(x, n)快速幂算法
实现 pow(x, n) ,即计算 x
的整数 n
次幂函数(即,xn
)。此函数应将 x
作为浮点数(意味着它可以是十进制数)和 n
作为整数(可以是正数、负数或零)一起使用。
快速幂(Exponentiation by Squaring) 的时间复杂度是 O(log n),而不是 O(n)。因此比普通连续相乘的暴力解法快很多,尤其在指数很大时更为明显。
快速幂利用了指数的 二进制分解。关键在于每次指数都除以 2(右移)。
代码:
class Solution {public double myPow(double x, int n) {// If power n is non-negative, calculate power using helper method// 如果指数 n 是非负数,直接调用辅助方法计算if (n >= 0) {return quickPow(x, n);} else {// If power n is negative, calculate the inverse of the power// 如果指数 n 是负数,先转成 long 类型防止溢出,然后计算倒数return 1 / quickPow(x, -(long) n);}}private double quickPow(double base, long exponent) {double result = 1; // Initialize result to neutral element for multiplication// 初始化结果为 1(乘法的单位元)// Loop through all bits of the exponent// 遍历指数的每一位(二进制)while (exponent > 0) {// If the current bit is set, multiply the result by the base// 如果当前位是 1(即指数是奇数),说明该位有效,就把当前 base 乘进结果中if ((exponent & 1) == 1) {result *= base;}// Square the base for the next bit in the exponent// 每处理一位,把 base 平方,指数除以 2,平方乘法base *= base;// Shift exponent to the right to process the next bit// 指数右移一位,继续处理下一个最低位exponent >>= 1;}// Return the final result of base raised to the exponent// 返回最终结果return result;}
}
平方乘法的数学原理
我们知道:
-
x² = x * x
-
x⁴ = (x²)²
-
x⁸ = (x⁴)²
也就是说:
x^2k = (x^k)^2
这说明:
如果我们每次把底数平方,就相当于一次性“处理了两个幂”。
⛳ 示例过程:a = 2, n = 13
n | n 的二进制 | 当前位 | result 操作 | base 操作 | 新 result | 新 base |
---|---|---|---|---|---|---|
13 | 1101 | 1 | result *= base | base = base² | 2 | 4 |
6 | 0110 | 0 | - | base = base² | 2 | 16 |
3 | 0011 | 1 | result *= base | base = base² | 32 | 256 |
1 | 0001 | 1 | result *= base | base = base² | 8192 | 65536 |
0 | 0000 | - | 结束 |
如果指数 n 是负数,先转成 long 类型防止溢出
Java 中 int
类型的取值范围是:
👉 [-2³¹, 2³¹ - 1]
👉 即 [-2147483648, 2147483647]
int n = Integer.MIN_VALUE; // n = -2147483648
int positive = -n; // 正常来说你想让它变成 2147483648
System.out.println(positive); // 实际输出:-2147483648(依然是负数!)
为什么?因为 2147483648 超出了 int 最大值!
✅ 解决方法:先转成 long
return 1 / quickPow(x, -(long) n);
这样 -(long) n 的计算就不会发生溢出了:
long
是 64 位的,能表示的范围非常大:
-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
比 int
的表示范围大得多,所以:
long n = Integer.MIN_VALUE; // n = -2147483648 long positive = -n; // 不会溢出 System.out.println(positive); // 输出:2147483648 ✅
🔍 为什么这在快速幂中很重要?
因为我们要把 n 转为正数,才能做快速幂:
如果你不转为 long,那么:
quickPow(x, -n); // 这里 -n 就可能等于 Integer.MIN_VALUE
就会导致逻辑错误甚至死循环(因为指数没变正)。
📘 看一下几个重要值及其补码:
十进制值 | 二进制补码表示 | 注释说明 |
---|---|---|
-2147483648 | 10000000 00000000 00000000 00000000 | 最小的 int,符号位为 1,其他全 0 |
-2147483647 | 10000000 00000000 00000000 00000001 | 第二小,最低位是 1 |
-1 | 11111111 11111111 11111111 11111111 | 补码中所有位都是 1 |
0 | 00000000 00000000 00000000 00000000 | 全 0 |
1 | 00000000 00000000 00000000 00000001 | 正数,从 1 开始递增 |
2147483647 | 01111111 11111111 11111111 11111111 | int 能表示的最大值 |
补码的优点:正负数加法可以统一处理(硬件电路简单)
为什么溢出会“绕回原值”?
Java 中的 int
是固定长度的 32 位,有符号整数。
当你进行超出范围的计算时,多出来的部分会被截断,留下的低 32 位成为新的值。
这就像一个指针在一个圆圈里走路,走过最大值后,就绕到了最小值。
为什么右移?
因为在快速幂算法中,我们是从低位(最右边)开始处理二进制位的,所以需要不断右移指数,把最低位移出去,这样我们就能一位一位检查该不该乘上当前的 base
。
-
右移一位(>> 1):相当于除以 2 向下取整
-
左移一位(<< 1):相当于乘以 2
我们在快速幂中需要不断除以 2,是为了把 exponent
处理完(直到它变成 0)。
相关文章:
50. Pow(x, n)快速幂算法
实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。此函数应将 x 作为浮点数(意味着它可以是十进制数)和 n 作为整数(可以是正数、负数或零)一起使用。 快速幂(Expo…...
Python函数
三.函数进阶 0.定义 函数三要素:函数名,参数,返回值,其中只有函数名是必须要的,参数,返回值可以没有 语法: def 函数名(参数): 函数体 return 返回值 1.…...
7.Spring框架
# spring框架Spring3.0开启了纯注解开发模式,使用Java类替代配置文件,开启了Spring快速开发赛道## 为什么要使用 **Spring** 框架? Spring 是一个轻量级应用框架,它提供了 IoC 和 AOP 这两个核心的功能。它的核心目的是为了…...
计算机网络-----详解HTTP协议
✏️1. 什么是HTTP HTTP (全称为 “超⽂本传输协议”) 是⼀种应⽤⾮常⼴泛的应⽤层协议(所谓 “超⽂本” 的含义, 就是传输的内容不仅仅是⽂本(⽐如 html, css 这个就是⽂本), 还可以是⼀些其他的资源, ⽐如图⽚, 视频, ⾳频等⼆进制的数据)。 HTTP 诞⽣…...
解决npm安装依赖报错ERESOLVE unable to resolve dependency tree
在使用 npm 安装项目依赖时,有时会遇到错误信息 “npm ERR! code ERESOLVE”,该错误通常发生在依赖版本冲突或者依赖解析问题时。本文将详细介绍出现这个错误的原因,并提供解决方法,确保正确安装项目依赖并避免该错误的发生。 一…...
微信小程序安卓手机输入框文字飘出输入框
最近在开发微信小程序遇到一个问题,安卓手机输入框文字飘出输入框,但是ios系统的手机则正常。 使用情景:做了一个弹窗,弹窗内是表单,需要填写一些信息,但是在填写信息时光标不显示,输入的内容飘…...
python网络自动化-数据格式与数据建模语言
数据格式 在Python网络运维自动化最基本是JSON、YAML和XML这3种数据格式。除了这3种常用的数据格式,还有一种深受网络工程师喜爱且在网络运维自动化中常用的数据承载方式——表格 需要注意的是JSON的键必须用双引号包裹,JSON的对象数据键值对的值和数组…...
C++ 中的 atan2 函数:深入解析与应用
在 C 编程中,数学计算是许多应用场景的核心,例如几何问题、物理模拟和游戏开发等。atan2 函数作为数学库中的一个重要工具,提供了比普通反正切函数更强大的功能。本文将深入解析 atan2 函数的原理、使用方法以及实际应用场景,并通…...
云计算-Azure Functions :构建事件驱动的云原生应用报告
云计算导论 课程研究报告 Azure Functions :构建事件驱动的云原生应用 摘要: Azure Functions 是一种无服务器解决方案,是由微软 Azure 平台提供的,可以使用户专注于业务逻辑,减少代码的编写,减少需要维护…...
【笔记——李沐动手学深度学习】2.3 线性代数
2.3.1 标量 标量由只有一个元素的张量表示。 下面的代码将实例化两个标量,并执行一些熟悉的算术运算,即加法、减、乘法、除法和指数。 2.3.2 向量 人们通过一维张量表示向量。一般来说,张量可以具有任意长度,取决于机器的内存限…...
多个 Job 并发运行时共享配置文件导致上下文污染,固化 Jenkins Job 上下文
基于 context.py 固化 Jenkins Job 上下文的完整方案,适用于你当前的工作流(Python Jenkins Pipeline),解决: 多个 Job 并发运行时共享配置文件导致上下文污染;读取环境变量或 JSON 文件时被其他 Job 修改…...
github 上的php项目
github 上的php项目 项目的网址 (Loong1996/LikeGirlSite: 情侣网站、情侣网页、恋爱记录网站) # 修改 # admin/Config_DB.php//localhost 为数据库地址 一般使用默认的即可 或(127.0.0.1) $db_address "mysql_php";/…...
防火墙快速管理软件,66K超小巧
软件介绍 今天为大家推荐一款轻量级的Windows防火墙管理工具,这款工具能帮助用户快速开启或关闭系统防火墙功能,操作比系统原生设置更加便捷高效。 软件优势 相比通过系统设置层层点击的操作方式,这款仅66KB大小的微型工具只需单击按钮…...
入门级STM32F103C8T6无人机遥控(原理图)
一、STM32主控电路 一、STM32 主控电路 把 STM32 想象成 “机器人的大脑”,核心电路是 “大脑的基础保障”:让大脑有电、有心跳(时钟 )、能复活(复位 )。 1. 电源引脚(VDD、VDDA、VSS 等 &#…...
无人机灯光驱动模块技术解析
一、运行方式 1. 核心流程: 指令接收:灯光控制模块通过无线通信链路(如WiFi, 数传电台,或专用的表演控制链路)接收来自地面站或中央控制系统的灯光指令。指令包含:颜色(RGB/RGBW值࿰…...
React + Umi(Umijs/Max) 搭建项目及配置
文章标题 01 环境准备02 快速构建2.1 参数选项2.2 umix 还是 umijs/max2.3 使用 pnpm (推荐)2.4 使用 npm 和 yarn2.5 启动项目2.6 启用 Prettier(可选)2.7 打包部署发布 03 Tailwind CSS 插件(可选)3.1 安…...
React 第六十四节Router中HashRouter的使用详细介绍及案例分析
前言 HashRouter 是 React Router 提供的一种路由实现方案,它使用 URL 的 hash 部分(# 后面的内容)来实现客户端路由功能。 一、HashRouter 的核心用途 客户端路由:在不刷新页面的情况下管理应用导航兼容性:支持不支…...
Linux RDMA网络配置手册
一、配置前准备工作 在进行 RDMA 网络配置之前,请确保以下准备工作已完成: 硬件环境 确保服务器支持 RDMA 功能,例如支持 InfiniBand 或 RoCE(RDMA over Converged Ethernet)的网卡。确保网络交换设备支持 RDMA 协议…...
sentinel与seata组件在微服务中的基本作用
微服务基础内容: 在微服务中,首先学习了微服务的横向拆分与纵向拆分,纵向拆分指按照功能拆分模块,横向拆分指将高复用的模块单独拆分,使纵向拆分的模块去调用这部分内容。 学习了基本拆分后,需要知道微服…...
Springboot 集成多数据源pgSql+mysql,启动报错
一.错误信息: 2025-06-25 20:25:50.870 ERROR [ai-manage-center,,] --- [ruid-ConnectionPool-Create-1057240219] DruidDataSource : create connection SQLException, url: jdbc:postgresql://10.10.60.227:5432/ai_dify1?sslmodedisable¤tSchemapub…...
南宫28NG相信品牌力量/Vue 3 中的组合式 API(Composition API)进阶实战
南宫28NG相信品牌力量【罔丨止:MGTY.PW】 点击此处复制到浏览器打开 随着 Vue 3 的普及,Composition API 已成为现代 Vue 开发的主流。本节我们将深入掌握组合式 API 的进阶用法,涵盖响应式工具、生命周期钩子封装、自定义逻辑抽离等关键技术…...
实战使用 Docker Compose 搭建 Redis Cluster 集群
文章目录 前言技术积累Docker Compose简介Redis Cluster简介Redis Cluster 解决的问题 实战演示部署环境创建目录编写Redis配置文件编写Docker-Compose.yml执行yml文件,启动容器查看容器状态创建集群验证集群集群数据验证 总结 前言 随着互联网技术的发展ÿ…...
Tauri(2.5.1)+Leptos(0.8.2)开发自用桌面小程序--DeepSeek辅助编程(俄罗斯方块)
在之前工作基础上(Tauri(2.5.1)Leptos(0.8.2)开发自用桌面小程序-CSDN博客),继续进行自用桌面小程序的开发,这次完全使用DeepSeek辅助编程做一个俄罗斯方块游戏,大部分代码由DeepSeek自主完成,Bug扔给DeepS…...
flex布局实例:把色子放进盒子里
目录 一、flex布局实例:把色子放进盒子里 1、基础样式 二、justify-content 属性 三、flex-direction 属性 四、align-items 属性 五、flex-wrap 属性 二、flex布局应用到常见场景 非常详细的讲解flex布局,看一看,练一练! …...
【启发式算法】RRT*算法详细介绍(Python)
📢本篇文章是博主人工智能(AI)领域学习时,用于个人学习、研究或者欣赏使用,并基于博主对相关等领域的一些理解而记录的学习摘录和笔记,若有不当和侵权之处,指出后将会立即改正,还望谅…...
基于R语言的亚组分析与森林图绘制1
亚组分析是临床研究中的重要分析方法,其核心是通过将研究对象按基线特征(如年龄、性别或吸烟状况等)划分为不同亚组,进而评估干预措施或暴露因素在各亚组中对结局影响的差异性。 在亚组分析中,交互作用(P for interaction)是关键指标,用于判断干预措施或暴露因素与亚组…...
idea, CreateProcess error=206, 文件名或扩展名太长
idea, CreateProcess error206, 文件名或扩展名太长 解决 “CreateProcess error206, 文件名或扩展名太长” 错误 CreateProcess error206 是 Windows 系统特有的错误,表示命令行参数超出了 Windows 的 32767 字符限制。这个问题在 Java 开发中尤其常见,…...
aspose.word在IIS后端DLL中高并发运行,线程安全隔离
aspose.word在IIS后端DLL中运行,加载很慢,如何为全部用户加载,再每个用户访问时在各自线程中直接可以打开WORD文件处理 Aspose.Words 在 IIS 中优化加载性能方案 针对 Aspose.Words 在 IIS 后端 DLL 中加载缓慢的问题,我们可以通过单例模式预加载组件并结合线程安…...
day042-负载均衡与web集群搭建
文章目录 0. 老男孩思想-面试官问:你对加班的看法?1. 负载均衡2. 搭建负载均衡的WordPress集群2.1 负载均衡服务器2.2 配置web服务器2.3 测试 踩坑记录1. /var/cache/nginx权限问题 0. 老男孩思想-面试官问:你对加班的看法? 互联网公司没有不加班的&a…...
DuDuTalk | 武汉赛思云科技有限公司通过武汉市人工智能企业认定!
近日,2025年武汉市人工智能企业名单正式公布!武汉赛思云科技有限公司(以下简称赛思云科技)凭借卓越的技术实力与创新成果,成功入选武汉市人工智能企业。这是对公司长期深耕AI语音智能领域、推动数字化转型的高度认可&a…...
Tita CRM飞书协同版:解锁企业销售与交付管理新效能
数字化转型的破局之道 在数字经济加速发展的今天,传统管理模式正面临前所未有的挑战: • 销售过程缺乏可视化管控手段 • 项目执行存在严重的信息孤岛 • 跨部门协作效率持续低下 • 绩效考核缺乏客观数据支撑 Tita CRM作为专业的智能化管理平台&#x…...
web安全之h2注入系统学习
起初是在N1 Junior 2025 上面碰到一题,考点是h2的sql注入。由于之前没有见过,趁此机会系统学习一番 实验代码 public class H2Inject {public static void main(String[] args) throws Exception{JdbcDataSource dataSource new JdbcDataSource();dataS…...
LVS-DR负载均衡群集深度实践:高性能架构设计与排障指南
目录 一、核心原理与理论 二、背景与架构设计 三、全流程部署步骤 1. NFS共享存储配置(192.168.7.100) 2. Real Server节点配置(四台服务器) 3. Director服务器配置 四、常见问题解决方案 五、生产环境总结 拓扑示意图&am…...
Java如何导出word(根据模板生成),通过word转成pdf,放压缩包
<!-- 导出word文档所需依赖--><dependency><groupId>com.deepoove</groupId><artifactId>poi-tl</artifactId><version>1.10.0-beta</version></dependency><dependency><groupId>org.apache.poi</gr…...
.NET 7.0 EF Core:一、创建Web API 项目基础框架和用户表的增删改查
demo 地址: https://github.com/iotjin/Jh.Admin.NETCore 代码不定时更新,请前往github查看最新代码 .NET 7.0 EF Core:一、创建Web API项目 官方教程序一、项目目录结构各层职责说明1️⃣ Admin.NETCore.API(接口层)2️⃣ Admin.…...
一篇文章了解XML
一、什么是 XML? XML 是一种结构化数据的标记语言,用来存储、传输和描述数据。 它和 HTML 很像,但它的标签是自定义的,不限定格式和外观,而是强调数据的结构和含义。 XML不是用来展示数据的,HTML是用来展…...
Windows下安装zookeeper
有关Linux安装zk的文章可以参考下我之前写的: Zookeeper 3.8.4 安装和参数解析 Windows下的下载和Linux是一样的,都是同一个包,目前zk稳定版是 3.8.4 下载解压后 在根目录下创建 data 文件夹用来存放数据文件 在 conf 文件夹中,…...
计算机网络 网络层:控制平面
在本章中,包含网络层的控制平面组件。控制平面作为一种网络范围的逻辑,不仅控制沿着从源主机到目的主机的端到端路径间的路由器如何转发数据报,而且控制网络层组件和服务如何配置和管理。5.2节,传统的计算图中最低开销路径的路由选…...
探索阿里云智能媒体管理IMM:解锁媒体处理新境界
一、引言:开启智能媒体管理新时代 在数字化浪潮的席卷下,媒体行业正经历着前所未有的变革。从传统媒体到新媒体的转型,从内容生产到传播分发,每一个环节都在寻求更高效、更智能的解决方案。而云计算,作为推动这一变革…...
微信点餐小程序—美食物
本项目是基于WAMP Server 和PHP 动态网页技术构建的微信小程序点餐系统,该系统主要分为前端(微信小程序)和后端(基于PHPMySQL服务器端) 整体架构流程 1、前端部分 用户界面:展示菜品、处理用户点餐操作、…...
Python零基础入门到高手8.5节: 实现选择排序算法
目录 8.5.1 排序算法简介 8.5.2 选择排序算法 8.5.3 好好学习,天天向上 8.5.1 排序算法简介 所谓排序,是指将数据集合中的元素按从小到大的顺序进行排列,或按从大到小的顺序进行排列。前者称为升序排序,后者称为降序排序。在数…...
JavaEE初阶第四期:解锁多线程,从 “单车道” 到 “高速公路” 的编程升级(二)
专栏:JavaEE初阶起飞计划 个人主页:手握风云 目录 一、Thread类及常用方法 2.1. Thread的常见构造方法 2.2. Thread的常见属性 2.3. 启动一个线程 2.4. 中断一个线程 2.5. 等待一个线程 2.6. 休眠当前线程 一、Thread类及常用方法 2.1. Thread的…...
Metasploit常用命令详解
一、Metasploit 概述 Metasploit是一款开源的渗透测试框架,由 H.D. Moore 于 2003 年首次发布,目前由 rapid7 公司维护。它整合了大量漏洞利用模块、后渗透工具和漏洞扫描功能,已成为网络安全工程师、红队 / 蓝队成员及安全研究人员的核心工…...
2025.6.24总结
今天发生了两件事,这每件事情都足以影响我的工作状态。 1.团队中有人要转岗 这算是最让我有些小震惊的事件了。我不明白,那个同事干得好好的,为啥会转岗,为啥会被调到其他团队。虽然团队有正编,有od,但我自始自终觉得…...
2023年全国青少年信息素养大赛Python 复赛真题——玩石头游戏
今日python每日练习题为——玩石头游戏,大家记得坚持刷题哦,闯入国赛~ 每轮可拿 1-3 块石头,双方均采取最优策略。若石头数 n 为 4 的倍数,无论先手取 k 块(1≤k≤3),后手总能取 4-k 块…...
MySQL之SQL性能优化策略
MySQL之SQL性能优化策略 一、主键优化策略1.1 主键的核心作用1.2 主键设计原则1.3 主键优化实践 二、ORDER BY优化策略2.1 ORDER BY执行原理2.2 ORDER BY优化技巧2.3 处理大结果集排序 三、GROUP BY优化策略3.1 GROUP BY执行原理3.2 GROUP BY优化方法 四、LIMIT优化策略4.1 LIM…...
AI时代工具:AIGC导航——AI工具集合
大家好!AIGC导航是一个汇集多种AIGC工具的平台,提供了丰富的工具和资源。 工具功能: 该平台整合了多样的AIGC工具,涵盖了绘画创作、写作辅助以及视频制作等多个领域。绘画工具能够生成高质量的图像作品;写作工具支持从构思到润色的全流程写…...
性能测试-jmeter实战4
课程:B站大学 记录软件测试-性能测试学习历程、掌握前端性能测试、后端性能测试、服务端性能测试的你才是一个专业的软件测试工程师 性能测试-jmeter实战4 jmeter环境搭建1. 安装Java环境(必需) JMeter环境搭建完整指南1. 安装Java࿰…...
C++字符串的行输入
1、字符串的输入 下面用一个真实的示例来进行演示: #include<iostream> #include<string>int main() {using namespace std;const int ArSize 20;char name[ArSize];char dessert[ArSize];cout << "Enter your name:\n";cin >>…...
【Linux网络与网络编程】15.DNS与ICMP协议
1. DNS 1.1 DNS介绍 TCP/IP 中使用 IP 地址和端口号来确定网络上的一台主机的一个程序,但是 IP 地址不方便记忆,于是人们发明了一种叫主机名的字符串,并使用 hosts 文件来描述主机名和 IP 地址的关系。最初, 通过互连网信息中心(SRI-NIC)来…...