超长正整数的加法
一、引言
在计算机科学中,整数加法是一个基础且重要的操作。然而,当面对超长正整数(即超出计算机内置整数类型表示范围的整数)时,传统的整数加法方法便不再适用。超长正整数通常使用字符串或数组来表示,每一位对应整数的一个数字。因此,实现超长正整数的加法就需要一些特殊的技巧和算法。本文将详细探讨如何实现超长正整数的加法,并提供C++代码示例。
二、算法设计
超长正整数的加法算法可以借鉴手工进行大数加法的思路。具体步骤如下:
- 从最低位(即字符串的末尾或数组的尾部)开始,逐位相加。
- 将每一位的加法结果(0-18)分为两部分:进位(0或1)和当前位的值(0-9)。
- 将进位加到下一位的加法结果中,并重复步骤2,直到所有位都处理完毕。
- 如果最高位仍有进位,需要在结果前添加一个数字“1”。
- 转换回字符串或数组形式,得到最终的加法结果。
三、C++代码实现
下面是一个使用C++实现的超长正整数加法的示例代码:
#include <iostream>
#include <string>
#include <algorithm>// 辅助函数:将两个数字相加并返回结果和进位
std::pair<int, int> addDigits(int a, int b, int &carry) {int sum = a + b + carry;carry = sum / 10;return {sum % 10, carry};
}// 超长正整数加法函数
std::string addBigNumbers(const std::string &num1, const std::string &num2) {// 反转字符串以便从最低位开始相加std::string reversedNum1 = num1;std::string reversedNum2 = num2;std::reverse(reversedNum1.begin(), reversedNum1.end());std::reverse(reversedNum2.begin(), reversedNum2.end());// 确保num1是较长的数if (reversedNum2.size() > reversedNum1.size()) {std::swap(reversedNum1, reversedNum2);}// 初始化结果字符串和进位std::string result;int carry = 0;// 逐位相加for (size_t i = 0; i < reversedNum1.size(); ++i) {int digit1 = reversedNum1[i] - '0';int digit2 = (i < reversedNum2.size()) ? (reversedNum2[i] - '0') : 0;auto [sumDigit, newCarry] = addDigits(digit1, digit2, carry);result.push_back(sumDigit + '0');carry = newCarry;}// 处理最高位的进位if (carry > 0) {result.push_back(carry + '0');}// 反转结果字符串并返回std::reverse(result.begin(), result.end());return result;
}// 主函数
int main() {std::string num1, num2;std::cout << "请输入第一个超长正整数:";std::cin >> num1;std::cout << "请输入第二个超长正整数:";std::cin >> num2;std::string sum = addBigNumbers(num1, num2);std::cout << "两数之和为:" << sum << std::endl;return 0;
}
四、代码解释
addDigits函数:这是一个辅助函数,用于将两个数字和一个进位相加,并返回结果和新的进位。addBigNumbers函数:这是实现超长正整数加法的核心函数。首先,它反转输入的两个字符串,以便从最低位开始相加。然后,它遍历较短的字符串(或两个字符串中的每一位),逐位相加,并使用addDigits函数处理进位。最后,它处理最高位的进位(如果有的话),并反转结果字符串以得到正确的顺序。main函数:这是程序的主入口。它首先接收用户输入的两个超长正整数,然后调用addBigNumbers函数计算它们的和,并输出结果。
五、性能优化与边界情况处理
在实现超长正整数的加法时,除了基本的算法设计外,我们还需要考虑一些性能优化和边界情况的处理。
1. 性能优化
- 预分配内存:在构建结果字符串时,我们可以预先估计结果字符串的长度,并一次性分配足够的内存空间。这样可以避免在添加新字符时频繁地重新分配内存,从而提高性能。
- 避免不必要的字符串反转:在上面的示例代码中,我们对输入字符串进行了两次反转操作(一次是为了从最低位开始相加,另一次是为了得到正确的结果顺序)。我们可以优化这个步骤,只进行一次反转操作,即在生成结果字符串时直接按照正确的顺序添加字符。
2. 边界情况处理
- 空字符串或零值:当输入字符串为空或表示零值时,我们需要特殊处理。例如,如果两个输入字符串都是空字符串或表示零值,则结果也应该是一个空字符串或表示零值。
- 前导零:在生成结果字符串时,我们可能需要删除前导零。虽然前导零在数学上不影响整数的值,但在某些应用中可能需要将它们删除以获得更简洁的表示。
3. 错误处理
- 非法输入:我们应该确保输入字符串只包含有效的数字字符。如果输入包含非数字字符,我们应该能够检测并处理这种错误情况。
- 溢出处理:虽然超长正整数的加法本身不会导致溢出(因为我们可以使用任意长度的字符串或数组来表示结果),但在某些情况下,我们可能需要处理与超长正整数加法相关的溢出问题。例如,当我们试图将结果存储在一个固定长度的变量中时,可能会发生溢出。在这种情况下,我们应该能够检测并处理这种错误情况。
4. 示例代码优化
下面是一个优化后的示例代码,它包含了上述提到的一些改进:
#include <iostream>
#include <string>
#include <stdexcept>// 辅助函数:将两个数字相加并返回结果和进位
std::pair<int, int> addDigits(int a, int b, int &carry) {int sum = a + b + carry;carry = sum / 10;return {sum % 10, carry};
}// 超长正整数加法函数(优化版)
std::string addBigNumbers(const std::string &num1, const std::string &num2) {if (num1.empty() && num2.empty()) {return "0"; // 如果两个数都是空字符串,则返回"0"}// 确保num1是较长的数std::string maxNum = num1;std::string minNum = num2;if (num2.size() > num1.size()) {std::swap(maxNum, minNum);}int carry = 0;std::string result;int i = maxNum.size() - 1, j = minNum.size() - 1;// 逐位相加while (i >= 0) {int digit1 = i >= 0 ? maxNum[i] - '0' : 0; // 处理maxNum的剩余位数int digit2 = j >= 0 ? minNum[j] - '0' : 0; // 处理minNum的剩余位数auto [sumDigit, newCarry] = addDigits(digit1, digit2, carry);result.push_back(sumDigit + '0');carry = newCarry;--i;--j;}// 处理最高位的进位if (carry > 0) {result.push_back(carry + '0');}// 去除前导零(如果有的话)while (!result.empty() && result.front() == '0') {result.erase(0, 1);}return result;
}// 主函数(略)
// ...
在这个优化后的示例代码中,我们添加了对空字符串和零值的特殊处理,并在逐位相加时直接处理了两个输入字符串的剩余位数。此外,我们还添加了一个去除前导零的步骤,以确保结果字符串的简洁性。
相关文章:
超长正整数的加法
一、引言 在计算机科学中,整数加法是一个基础且重要的操作。然而,当面对超长正整数(即超出计算机内置整数类型表示范围的整数)时,传统的整数加法方法便不再适用。超长正整数通常使用字符串或数组来表示,每…...
C++ - 查找算法 和 其他 算法
目录 一. 查找算法: 1.顺序查找: 2.二分查找: 二. 其他算法: 1.遍历算法: 2.求和、求平均值等聚合算法。 a.求和算法: b.求平均值算法: 一. 查找算法: 1.顺序查找࿱…...
字符串的信号(SIGNAL)和槽(SLOT)的宏连接方式弊端
字符串的信号(SIGNAL)和槽(SLOT)的宏连接方式在 Qt 4 及早期版本中广泛使用,但这种方法确实存在一些缺点,主要包括以下几点: 类型安全性缺失:由于 SIGNAL 和 SLOT 宏接受的是字符串参…...
Kali linux学习入门
Kali linux学习入门 文章目录 Kali linux学习入门Kali Linux简介Kali Linux工具篇Kali Docker安装Docker 更换国内镜像源Kali 安装 docker compose Kali Linux文档篇Kali Linux 社区篇 Kali Linux简介 Kali Linux是专门用于渗透测试linux操作系统,它由BackTrack发展…...
selenium中,怎么判断是否已选多选框
html文件 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title> </head> <body><p>测试勾选</p><div><input type"checkbox" name"b…...
WindowManager相关容器类
窗口中容器类介绍: 本节内容较多,建议结合前面的内容一起阅读: 1、addWindow的宏观概念 2、WindowManager#addView_1 3、WindowManager#addView_2 1)、WindowContainer: class WindowContainer<E extends WindowC…...
零售行业运营有哪些业务场景?详解各业务场景的分析指标和维度
在当今这个数字化迅速发展的时代,零售行业正经历着前所未有的变革。传统的零售模式正在被新兴的技术和创新的业务场景所颠覆,消费者的需求和购物习惯也在不断地演变。零售行业的运营,作为连接消费者、产品和市场的关键环节,对于零…...
无锡哲讯携手SAP,赋能装备制造业数字化转型
在当今快速发展的工业4.0时代,装备制造业作为国民经济的重要支柱,正面临着前所未有的机遇与挑战。无锡哲讯智能科技有限公司凭借其深厚的行业经验和专业的SAP实施能力,为装备制造业提供全面的数字化解决方案,助力企业实现智能化、…...
TPM仿真环境搭建
文章目录 背景及注意事项一、CMake二、m4三、GNU MP Library四、TPM_Emulator五、TSS协议栈(trousers-0.3.14.tar.gz)六、 tpm-tools七、查看是否安装成功八、测试 TPM环境(需要开三个终端分别运行)8.1 启动TPM (第一个…...
提高篇(五):使用Processing创作互动艺术:从灵感到实现
提高篇(五):使用Processing创作互动艺术:从灵感到实现 引言 互动艺术将观众从被动的观察者转变为主动参与者,通过创意编程和技术手段,让艺术品具备感知和回应的能力。Processing作为一种强大的创意编程工具,提供了丰富的功能和灵活的编程环境,帮助艺术家和设计师实现他…...
华为od-C卷100分题目-3用连续自然数之和来表达整数
华为od-C卷100分题目-3用连续自然数之和来表达整数 题目描述 一个整数可以由连续的自然数之和来表示给定一个整数,计算该整数有几种连续自然数之和的表达式,且打印出每种表达式 输入描述 一个目标整数T(1<T<1000) 输出描述 该整数的所有表达…...
Chrome 自动执行 JS 脚本 | Tampermonkey 插件
文章目录 第 1 步:安装插件 Tampermonkey第 2 步:固定到工具栏第 3 步:在网站上启用 Tampermonkey第 4 步:查看效果第 5 步:调试 JS 代码😂 背景:有个网站,每次进去都要点 3 次才能把相关页面展开。而且,页面经常会自己刷新,导致展开的页面又收回去了。【这一天天的…...
ffmplay 源码解读
stream_open 讲解 // 定义一个静态函数用于初始化并返回VideoState结构体指针,用于管理播放状态 static VideoState* stream_open(const char* filename, AVInputFormat* iformat) {VideoState* is; // 创建VideoState结构体指针// 分配内存并初始化VideoState结构…...
java web如何调用py脚本文件
Controller public class IndexController {RequestMapping("/pythonTest")ResponseBodypublic String pythonTest(){// 假设你的Python脚本名为script.pyString pythonScriptPath "D:\\project\\c1\\hello.py";ProcessBuilder processBuilder new Proce…...
K8s:无状态
无状态服务 无状态服务是指服务的实例之间没有持久化状态,每个实例都是相同的,可以互换使用。 调度器 ReplicationController 简称 RC是 Kubernetes 早期版本中用来确保 Pod 副本始终运行的 API 对象。它通过监控 Pod 副本的数量,确保任何…...
Docker 入门篇(九)-- 使用 Maven 插件 构建 Docker 镜像
在这篇教程中,我们将学习如何使用 Maven 插件为 Spring Boot 应用构建 Docker 镜像。我们将使用 spring-boot-maven-plugin 和 dockerfile-maven-plugin 这两个插件。 一、前提条件 已安装 Docker。已安装 JDK 8 或以上版本。已安装 Maven。 二 创建一个 Spring …...
网络协议三
数据中心 一、DNS 现在网站的数目非常多,常用的网站就有二三十个,如果全部用 IP 地址进行访问,恐怕很难记住 根 DNS 服务器 :返回顶级域 DNS 服务器的 IP 地址 顶级域 DNS 服务器:返回权威 DNS 服务器的 IP 地址 …...
LeetCode LRU缓存
题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,…...
Parallels Desktop for Mac 19.4.0更新了哪些内容?有什么改进?
带来了重新设计的共享 Mac 文件夹版本,这些文件夹现在是符号链接,像指针一样指向您的 Mac 文件夹中的文件,同时仍然显示在 Windows 的本地磁盘上。 修复了由于共享文件夹问题导致 NinjaTrader 无法正常启动的问题。 修复了由于共享文件夹问…...
Python 将CSV文件转为PDF文件
CSV文件通常用于存储大量的数据,而PDF文件则是一种通用的文档格式,便于与他人共享和打印。将CSV文件转换成PDF文件可以帮助我们更好地管理和展示数据。本文将介绍如何通过Python编程将CSV文件导出为PDF文件。 Python Excel库安装及介绍 在 Python 中&am…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)
cd /home 进入home盘 安装虚拟环境: 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境: virtualenv myenv 3、激活虚拟环境(激活环境可以在当前环境下安装包) source myenv/bin/activate 此时,终端…...
车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...
第22节 Node.js JXcore 打包
Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本,基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...
WEB3全栈开发——面试专业技能点P8DevOps / 区块链部署
一、Hardhat / Foundry 进行合约部署 概念介绍 Hardhat 和 Foundry 都是以太坊智能合约开发的工具套件,支持合约的编译、测试和部署。 它们允许开发者在本地或测试网络快速开发智能合约,并部署到链上(测试网或主网)。 部署过程…...
