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

C++大整数类的设计与实现

1. 简介

我们知道现代的计算机大多数都是64位的,因此能处理最大整数为 2 64 − 1 2^{64}-1 2641。那如果是超过了这个数怎么办呢,那就需要我们自己手动模拟数的加减乘除了。

2. 思路

我们可以用一个数组来存储大数,数组中的每一个位置表示一个数位。为了方便,我们直接用 S T L STL STL中的vector来存。

2.1 大数加法

我们需要把两个大数的最低位对齐,然后再开始相加。唯一需要注意的是处理一下最高位置的进位置。

2.2 大数减法

大数减法跟加法不一样的是,我们需要处理相减后的前导0,因为有可能出现相减为0的情况。处理前导0只需要从最高位开始到第2位的连续0。

2.3 大数乘法

大数乘法与加法不同的是,每次相乘后放到相应的位置而不是相乘的位次本身。

2.4 大数除法

大数除法是最难的,我们用减法进行模拟。

假设两个大数为 a b a\ b a b a a a为除数, b b b为被除数。

我们每次需要找到最接近被除数的除数的进制次倍数 m m m

D 0 : = { d : a × 1 0 d ≤ b } d 0 = max ⁡ { D 0 } m 0 = a × 1 0 d 0 D_0 := \{d: a\times 10^d \le b\}\\ d_0 =\max \{D_0\}\\ m_0=a \times 10^{d_0} D0:={d:a×10db}d0=max{D0}m0=a×10d0
通过大数减法算出 t 0 = ⌊ b / m 0 ⌋ t_0 =\lfloor b/m_0 \rfloor t0=b/m0, 因此商需要加上 a n s = a n s + t 0 1 0 d 0 ans = ans +t_010^{d_0} ans=ans+t010d0

此时余数为 b 1 b_1 b1,如果 b 1 < a b_1<a b1<a,说明我们的除法做完了,否则令 b = b 1 b=b_1 b=b1, 继续重复上面的过程直到 b k < a b_k <a bk<a

2.5 符号问题

我们在加减乘除的时候,

可以将符号问题单独考虑。

因此可以写一个绝对值的大数相加,还有一个版本

的一个大的大数减一个小的大数的大数减法。

而至于乘除法的符号问题比较容易处理,因此可以

一同处理符号的问题。

3. 实现

放在gitee上了。

4. TODO

  • 更加丰富的测试样例
  • 加减乘除未兼容普通整数
  • 大数除法中的负数的商不是最小非负余数

相关文章:

C++大整数类的设计与实现

1. 简介 我们知道现代的计算机大多数都是64位的&#xff0c;因此能处理最大整数为 2 64 − 1 2^{64}-1 264−1。那如果是超过了这个数怎么办呢&#xff0c;那就需要我们自己手动模拟数的加减乘除了。 2. 思路 我们可以用一个数组来存储大数&#xff0c;数组中的每一个位置表…...

在 macOS 系统上安装 kubectl

在 macOS 系统上安装 kubectl 官网&#xff1a;https://kubernetes.io/zh-cn/docs/tasks/tools/install-kubectl-macos/ 用 Homebrew 在 macOS 系统上安装 如果你是 macOS 系统&#xff0c;且用的是 Homebrew 包管理工具&#xff0c; 则可以用 Homebrew 安装 kubectl。 运行…...

【人工智能】蓝耘智算平台盛大发布DeepSeek满血版:开创AI推理体验新纪元

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀ 蓝耘智算平台 蓝耘智算平台核心技术与突破元生代推理引擎快速入门&#xff1a;三步调用大模型接口&#xff0c;OpenAI SDK无缝兼容实战用例文…...

构建数据治理闭环:DAMA视角下的全流程实践与价值变现

随着数字经济的迅速发展&#xff0c;数据已成为企业核心资产&#xff0c;高效的数据治理体系正变得至关重要。本文基于DAMA理论&#xff0c;从数据资产入表、分类分级、确权登记到元数据管理、数据质量监控&#xff0c;再到数据集成、互操作及主数据管理&#xff0c;全流程构建…...

《深度剖析:AI与姿态估计技术在元宇宙VR交互中的应用困境》

在元宇宙的宏大版图里&#xff0c;虚拟现实&#xff08;VR&#xff09;交互是构建沉浸式体验的关键支柱&#xff0c;而人工智能&#xff08;AI&#xff09;与姿态估计技术的融合&#xff0c;本应成为提升交互体验的强大引擎。但在实际应用中&#xff0c;它们面临着诸多复杂且棘…...

【Python LeetCode】面试经典 150 题

数组 / 字符串快慢指针&#xff08;双指针&#xff09;总结88. 合并两个有序数组27. 移除元素26. 删除有序数组中的重复项80. 删除有序数组中的重复项 II Boyer-Moore 投票算法169. 多数元素扩展&#xff1a;寻找 n/3 多数元素 翻转法189. 轮转数组 贪心121. 买卖股票的最佳时机…...

2011-2019年各省乡镇综合文化站机构数数据

2011-2019年各省乡镇综合文化站机构数数据 1、时间&#xff1a;2011-2019年 2、来源&#xff1a;国家统计局、统计年鉴 3、指标&#xff1a;行政区划代码、地区、年份、乡镇综合文化站机构数 4、范围&#xff1a;31省 5、指标解释&#xff1a;乡镇综合文化站是中国基层文化…...

LeetCode 热题100 226. 翻转二叉树

LeetCode 热题100 | 226. 翻转二叉树 大家好&#xff0c;今天我们来解决一道经典的算法题——翻转二叉树。这道题在 LeetCode 上被标记为简单难度&#xff0c;要求我们翻转一棵二叉树&#xff0c;并返回其根节点。下面我将详细讲解解题思路&#xff0c;并附上 Python 代码实现…...

mysql 拼接多行合并为一行

如图所示&#xff0c;在variety相同的前提下拼接rating为ratingList&#xff0c;year_term为yearTermList sql如下&#xff1a; SELECT variety,GROUP_CONCAT(rating ORDER BY rating SEPARATOR ,) AS ratingList,GROUP_CONCAT(year_term ORDER BY year_term SEPARATOR…...

【Java项目】基于Spring Boot的论坛管理系统

【Java项目】基于Spring Boot的论坛管理系统 技术简介&#xff1a;采用Java技术、Spring Boot框架、MySQL数据库等实现。 系统简介&#xff1a;论坛管理系统是一个基于Web的在线平台&#xff0c;主要分为前台和后台两大功能模块。前台功能模块包括&#xff08;1&#xff09;首…...

unity学习54:图片+精灵+遮罩mask,旧版文本 text 和新的TMP文本

目录 1 图片 image 1.1 如果直接导入image 1.2 图片 image 和精灵 sprite 1.2.1 继续修改上面的格式 texture type 是default 1.2.2 再次关联到UI的 image 物体上就可以了 1.3 图片和遮罩 mask 1.3.1 创建1个父物体和1个子物体&#xff0c;分别都是image 1.3.2 如果父…...

2024年国赛高教杯数学建模D题反潜航空深弹命中概率问题解题全过程文档及程序

2024年国赛高教杯数学建模 D题 反潜航空深弹命中概率问题 原题再现 应用深水炸弹&#xff08;简称深弹&#xff09;反潜&#xff0c;曾是二战时期反潜的重要手段&#xff0c;而随着现代军事技术的发展&#xff0c;鱼雷已成为现代反潜作战的主要武器。但是&#xff0c;在海峡或…...

什么是数字人

什么是数字人 Ultralight-Digital-Human 是一个能在移动设备上实时运行的数字人模型仓库,可能是第一个开源的如此轻量级的数字人模型。 主要特点 轻量级:能够在移动设备上实时运行。开源:代码和模型公开,方便开发者使用和改进。文件结构 根目录: README.md:项目的说明文…...

15.5 基于 RetrievalQA 的销售话术增强系统实战:构建智能销售大脑

基于 RetrievalQA 的销售话术增强系统实战:构建智能销售大脑 关键词:RetrievalQA 应用实战、销售知识增强、语义检索优化、上下文感知问答、多源知识融合 1. RetrievalQA 技术原理与销售场景适配 1.1 RetrievalQA 核心工作机制 #mermaid-svg-VL2yIusgl4oprXUr {font-family…...

软件供应链安全工具链研究系列—RASP自适应威胁免疫平台(下篇)

在“软件供应链安全工具链研究系列—RASP自适应威胁免疫平台-上篇”中我们提到了RASP工具的基本能力、原理以及工具的应用场景&#xff0c;了解到了RASP工具在各场景下发挥的价值。那么在当今高强度攻防对抗的大场景下&#xff0c;RASP作为最后一道防线&#xff0c;不论是从高危…...

WordPress网站502错误全面排查与解决指南

502 Bad Gateway错误是WordPress站长最常遇到的服务器问题之一,它意味着服务器作为网关或代理时,未能从上游服务器获取有效响应。针对WP可能出现的502问题,本文提供一些基础到进阶的解决方案供大家参考:) 一、502错误的本质和核心诱因 502错误属于HTTP状态码中的5xx系列,…...

PCL源码分析:曲面法向量采样

文章目录 一、简介二、源码分析三、实现效果参考资料一、简介 曲面法向量点云采样,整个过程如下所述: 1、空间划分:使用递归方法将点云划分为更小的区域, 每次划分选择一个维度(X、Y 或 Z),将点云分为两部分,直到划分区域内的点少于我们指定的数量,开始进行区域随机采…...

HTTP 动态报错码的原因和解决方法

目录 1xx&#xff08;信息性状态码&#xff09; 2xx&#xff08;成功状态码&#xff09; 3xx&#xff08;重定向状态码&#xff09; 4xx&#xff08;客户端错误状态码&#xff09; 5xx&#xff08;服务器错误状态码&#xff09; 参考文章 以下是 HTTP 动态报错码的常见原…...

1分钟用DeepSeek编写一个PDF转Word软件

一、引言 如今&#xff0c;在线工具的普及让PDF转Word成为了一个常见需求&#xff0c;常见的pdf转word工具有收费的wps&#xff0c;免费的有pdfgear&#xff0c;见下文&#xff1a; PDFgear:一款免费的PDF编辑、格式转化软件-CSDN博客 还有网上在线的免费pdf转word工具smallp…...

生成对抗网络(GAN)

生成对抗网络&#xff08;GAN&#xff09;:生成对抗网络是一种深度学习模型&#xff0c;由 Ian Goodfellow 等人在 2014 年提出。GAN由生成器和判别器组成&#xff0c;生成器生成假数据&#xff0c;判别器区分真假数据。两者通过对抗训练不断提升&#xff0c;最终生成器能够生成…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

Spring事务传播机制有哪些?

导语&#xff1a; Spring事务传播机制是后端面试中的必考知识点&#xff0c;特别容易出现在“项目细节挖掘”阶段。面试官通过它来判断你是否真正理解事务控制的本质与异常传播机制。本文将从实战与源码角度出发&#xff0c;全面剖析Spring事务传播机制&#xff0c;帮助你答得有…...

代理服务器-LVS的3种模式与调度算法

作者介绍&#xff1a;简历上没有一个精通的运维工程师。请点击上方的蓝色《运维小路》关注我&#xff0c;下面的思维导图也是预计更新的内容和当前进度(不定时更新)。 我们上一章介绍了Web服务器&#xff0c;其中以Nginx为主&#xff0c;本章我们来讲解几个代理软件&#xff1a…...

短视频时长预估算法调研

weighted LR o d d s T p 1 − p ( 1 − p ) o d d s T p ( T p o d d s ∗ p ) o d d s p o d d s T o d d s odds \frac{Tp}{1-p} \newline (1-p)odds Tp \newline (Tp odds * p) odds \newline p \frac{odds}{T odds} \newline odds1−pTp​(1−p)oddsTp(Tpodds…...

Asp.net Core 通过依赖注入的方式获取用户

思路&#xff1a;Web项目中&#xff0c;需要根据当前登陆的用户&#xff0c;查询当前用户所属的数据、添加并标识对象等。根据请求头Authorization 中token&#xff0c;获取Redis中存储的用户对象。 本做法需要完成 基于StackExchange.Redis 配置&#xff0c;参考&#xff1a;…...

MySQL技术内幕1:内容介绍+MySQL编译使用介绍

文章目录 1.整体内容介绍2.下载编译流程2.1 安装编译工具和依赖库2.2 下载编译 3.配置MySQL3.1 数据库初始化3.2 编辑配置文件3.3 启动停止MySQL3.4 登录并修改密码 1.整体内容介绍 MySQL技术系列文章将从MySQL下载编译&#xff0c;使用到MySQL各组件使用原理源码分析&#xf…...

网络安全问题及对策研究

摘 要 网络安全问题一直是近年来社会乃至全世界十分关注的重要性问题&#xff0c;网络关乎着我们的生活&#xff0c;政治&#xff0c;经济等多个方面&#xff0c;致力解决网络安全问题以及给出行之有效的安全策略是网络安全领域的一大目标。 本论文简述了课题的开发背景&…...

SpringCloudAlibaba和SpringBoot版本问题

SpringCloudAlibaba和SpringBoot版本问题 直接参考官方给出的版本说明&#xff0c;具体地址&#xff1a;https://github.com/alibaba/spring-cloud-alibaba/wiki/%E7%89%88%E6%9C%AC%E8%AF%B4%E6%98%8E Spring Cloud Alibaba VersionSentinel VersionNacos VersionRocketMQ Ver…...

模拟搭建私网访问外网、外网访问服务器服务的实践操作

目录 实验环境 实践要求 一、准备工作 1、准备四台虚拟机&#xff0c;分别标号 2、 防火墙额外添加两块网卡&#xff0c;自定义网络连接模式 3、 关闭虚拟机的图形管理工具 4、关闭防火墙 5、分别配置四台虚拟机的IP地址&#xff0c;此处举一个例子&#xff08;使用的临…...