C++大整数的加减乘除

2024-04-27 19:36
文章标签 c++ 整数 加减乘除

本文主要是介绍C++大整数的加减乘除,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  大整数除法迅飞星火和文心一言给的算法可参考,但结果都不对。

(注意,_string 你用C++  std::string 代替就行)

 加法:

/// <summary>
/// 无符号的两个整数相加 (参考自星飞星火)
/// </summary>
/// <param name="num1"></param>
/// <param name="num2"></param>
/// <returns></returns>
/// 创建时间:2024-04-21    最后一次修改时间:2024-04-21 
_string _Integer::Add(const _string& num1, const _string& num2)
{/*int len1 = num1.size();int len2 = num2.size();int maxLen = std::max(len1, len2);std::string result(maxLen, '0');int iBorrow = 0;for (int i = 0; i < maxLen; i++) {int iDiff = num1[len1 - 1 - i] - num2[len2 - 1 - i] - iBorrow;if (iDiff < 0) {iDiff += 10;iBorrow = 1;}else {iBorrow = 0;}result[maxLen - 1 - i] = iDiff + '0';}result.erase(std::find_if(result.rbegin(), result.rend(), [](char ch) { return ch != '0'; }).base(), result.end());return result;*/int len1 = num1.std_size();int len2 = num2.std_size();int maxLen = _Math::Max(len1, len2);_string result(maxLen + 1, _t('0'));int carry = 0;for (int i = 0; i < maxLen; i++) {int sum = carry;if (i < len1) {sum += num1[len1 - 1 - i] - _t('0');}if (i < len2) {sum += num2[len2 - 1 - i] - _t('0');}carry = sum / 10;sum %= 10;result[maxLen - i] = sum + _t('0');}if (carry > 0) {result[0] = carry + _t('0');}else {//result.std_erase(result.std_begin());result.std_erase(0);}return result;
}

减法:

/// <summary>
/// 无符号的两个整数相减,部分算法参考自星飞星火,但星火
/// 算的结果只有同位数相减才正确,注意:这里是假定是无符
/// 号两个整数相减。
/// 【中文】:两个数相减
/// 【英文】:Subtract two numbers
/// 百度文心一言和星飞星火结果不对。
/// </summary>
/// <param name="num1"></param>
/// <param name="num2"></param>
/// <returns></returns>
/// 创建时间:2024-04-21    最后一次修改时间:2024-04-25 (已测试)
_string _Integer::Subtract(const _string& num1, const _string& num2, bool isCheckForamt)
{if (isCheckForamt){	Check(num1);	Check(num2);}/**   星火给出的代码:* int len1 = num1.size();int len2 = num2.size();int maxLen = std::max(len1, len2);std::string result(maxLen, '0');int iBorrow = 0;for (int i = 0; i < maxLen; i++) {int iDiff = num1[len1 - 1 - i] - num2[len2 - 1 - i] - iBorrow;if (iDiff < 0) {iDiff += 10;iBorrow = 1;}else {iBorrow = 0;}result[maxLen - 1 - i] = iDiff + '0';}result.erase(std::find_if(result.rbegin(), result.rend(), [](char ch) { return ch != '0'; }).base(), result.end());return result;*/int len1 = num1.Length;int len2 = num2.Length;int maxLen = _Math::Max(len1, len2);_string sResult(_t(""), maxLen + 1);//这里先比较字符串长度(数字位数)的大小if (len1 > len2){	 //num1 > num2int iBorrow = 0;for (int i = 0; i < len2; i++) {int iDiff = num1[len1 - 1 - i] - num2[len2 - 1 - i] - iBorrow;		 if (iDiff < 0) {iDiff += 10;iBorrow = 1;}else {iBorrow = 0;}sResult.Add(iDiff + _t('0'));} if (iBorrow != 0){bool bBorrow = false;for (int i = len2; i < len1; i++){_char c = num1[len1 - i - 1];if (!bBorrow){if (c == _t('0')) {sResult.Add(_t('9'));}else{sResult.Add(c - 1);bBorrow = true;}}else{sResult.Add(c);}}}else{for (int i = len2; i < len1; i++){_char c = num1[len1 - i - 1];sResult.Add(c);}}	sResult.TrimRight(_t('0'));  //除去尾部的0return sResult.Reversal();		 }else if(len1 == len2){//字符长度相等if (num1 > num2){int iBorrow = 0;for (int i = 0; i < len2; i++) {int iDiff = num1[len1 - 1 - i] - num2[len2 - 1 - i] - iBorrow;if (iDiff < 0) {iDiff += 10;iBorrow = 1;}else {iBorrow = 0;}sResult.Add(iDiff + _t('0'));}sResult.TrimRight(_t('0')); //除去尾部的0return sResult.Reversal();}else if(num1 == num2){return _t("0");}else{int iBorrow = 0;for (int i = 0; i < len2; i++) {int iDiff = num2[len1 - 1 - i] - num1[len2 - 1 - i] - iBorrow;if (iDiff < 0) {iDiff += 10;iBorrow = 1;}else {iBorrow = 0;}sResult.Add(iDiff + _t('0'));}sResult.TrimRight(_t('0')); //除去尾部的0sResult.Add(_t('-'));return sResult.Reversal();}}else{  //len1 < len2  小数减大数int iBorrow = 0;for (int i = 0; i < len1; i++) {int iDiff = num2[len2 - 1 - i] - num1[len1 - 1 - i] - iBorrow;if (iDiff < 0) {iDiff += 10;iBorrow = 1;}else {iBorrow = 0;}sResult.Add(iDiff + _t('0'));}if (iBorrow != 0) {  //还需借一位bool bBorrow = false;for (int i = len1; i < len2; i++) {_char c = num2[len2 - i - 1];if (!bBorrow) {if (c == _t('0')) {sResult.Add(_t('9'));}else {sResult.Add(c - 1);bBorrow = true;}}else {sResult.Add(c);}}}else {for (int i = len1; i < len2; i++) {_char c = num2[len2 - i - 1];sResult.Add(c);}}sResult.TrimRight(_t('0'));sResult.Add(_t("-"));return sResult.Reversal();}}

乘法

/// <summary>
/// 无符号的两个整数相剩 (参考自星飞星火)
/// 【中文】:两个数相乘
/// 【英文】:Multiplication of two numbers
/// </summary>
/// <param name="sNum1"></param>
/// <param name="sNum2"></param>
/// <returns></returns>
/// 创建时间:2024-04-21    最后一次修改时间:2024-04-21  (已测试)
_string _Integer::Multiplication(const _string& sNum1, const _string& sNum2,  bool isCheckForamt)
{if (isCheckForamt) { Check(sNum2);	Check(sNum2); }/*int len1 = num1.size();int len2 = num2.size();std::vector<int> result(len1 + len2, 0);for (int i = len1 - 1; i >= 0; i--) {for (int j = len2 - 1; j >= 0; j--) {int product = (num1[i] - '0') * (num2[j] - '0');int sum = result[i + j + 1] + product;result[i + j + 1] = sum % 10;result[i + j] += sum / 10;}}std::string res;for (int num : result) {if (!res.empty() || num != 0) {res.push_back(num + '0');}}return res.empty() ? "0" : res;*/size_t len1 = sNum1.Length;size_t len2 = sNum2.Length;_Array<_byte> result(len1 + len2);   //设置缓冲长度为 len1 + len2result.ZeroBufferAll();            //把缓冲区初始为0result.ResetLength(len1 + len2);  //重设长度/*1231133    (3)  i = 2 j = 1(个位+3) i + j = 3 刚好是第4位 (3) i = 2 j = 0  (十位加3)2211	________1353 */for (int i = len1 - 1; i >= 0; i--) {for (int j = len2 - 1; j >= 0; j--) {int product = (sNum1[i] - '0') * (sNum2[j] - '0'); //总量 n * nint sum = result[i + j + 1] + product;  //result[i + j + 1] = sum % 10; result[i + j] += sum / 10;}}_string sTmp(_t(""), result.Length);/*//15*15 = 0225  (第一位是0)size_t nStart = (*result.Data == 0) ? 1 : 0;for(size_t n = nStart; n < result.Length; ++n)		 sTmp.Add( *(result.Data + n) + 48);*/for (_byte b : result) {if (sTmp.Length > 0 || b != 0) {  //如果前面有非零的数字,则添加 sTmp.Add(b + 48);}}return sTmp.Length == 0 ? _t("0") : sTmp;
}

小整数整除

/// <summary>
/// sNum1 / sNum2 ,sNum1 的倍数受制于int所能表达的最大值
/// </summary>
/// <param name="sNum1"></param>
/// <param name="sNum2"></param>
/// <param name="isCheckForamt"></param>
/// <returns></returns>
/// 创建时间:2024-04-26    最后一次修改时间:2024-04-27  (已测试)
_Pair<int, _string> _Integer::SmallDiv(const _string& sNum1, const _string& sNum2, bool isCheckForamt)
{if (isCheckForamt) { Check(sNum1);	Check(sNum2); }if (sNum2 == _t("0")){d.PrintError(_t("除数不能为零"), _t("_Integer::SmallDiv"));assert(false);}if (sNum1.Length < sNum2.Length)return _Pair<int, _string>(0, sNum1);if (sNum1.Length == sNum2.Length){if (sNum1 > sNum2){int nNear = (sNum1[0] - 48) / (sNum2[0] - 48 ) + 1;for (int n = nNear; n > 0; --n){_string sn = ga.intToString(n);_string s = _Integer::Multiplication(sNum2, sn, false); //乘积_string r = _Integer::Subtract(sNum1, s, false); //余数if (r[0] == _t('-')){}else if (r == _t("0")){return _Pair<int, _string>(n, _t("0"));}	else{if (r.Length < sNum2.Length){return _Pair<int, _string>(n, r);}else if (r.Length == sNum2.Length){if (r < sNum2){return _Pair<int, _string>(n, r);}else if (r == sNum2){return _Pair<int, _string>(n + 1, _t("0"));}}}}}else if (sNum1 == sNum2){return _Pair<int, _string>(1, _t("0"));}else{return _Pair<int, _string>(0, sNum1);}}else //sNum1.Length > sNum2.Length{int nNear =  _Math::pow(10, sNum1.Length - sNum2.Length) * (sNum1[0] -48 + 1) - 1;//_pin(nNear);for (int n = nNear; n > 0; --n){_string sn = ga.intToString(n);_string s = _Integer::Multiplication(sNum2, sn, false); //乘积_string r = _Integer::Subtract(sNum1, s, false); //余数if (r[0] == _t('-')){}else if (r == _t("0")){return _Pair<int, _string>(n, _t("0"));}else{if (r.Length < sNum2.Length){return _Pair<int, _string>(n, r);}else if (r.Length == sNum2.Length){if (r < sNum2){return _Pair<int, _string>(n, r);}else if (r == sNum2){return _Pair<int, _string>(n + 1, _t("0"));}}}}}std::wcout <<  _t("错误:\n");_pcn(sNum1);_pcn(sNum2);assert(false);return _Pair<int, _string>(0, _t("错误!"));
}

大整数整除

/// <summary>
/// 【单词中英文对照】:两个数相除 - Divide two numbers
/// 
/// 百度文心一言和星飞星火结果不对。
/// </summary>
/// 创建时间:2024-04-25    最后一次修改时间:2024-04-27   (已测式,这个函数用了大约1整天时间,搞死人)
_string _Integer::Divide(const _string& sNum1, const _string& sNum2,bool isCheckForamt)
{	 if (isCheckForamt) { Check(sNum1);	Check(sNum2); }if (sNum2 == _t("0")){_string sError = _t("_string _Integer::Divide: 除数 sNum2 不能为零不能为 0  !");_cout << sError <<"\n";assert(false);		 }_string sResult(_t(""), sNum1.Length);//2024/4 nPos =  4-1 = 3     sSub = 24  Point = 2 - 1 - 1(2<4) = 0   s = sSub ""//2124/4 nPos =  4-1 = 3//2124/23 nPos = 4-2 - 1 = 1_string sSub = sNum1.SubStr(0, sNum2.Length); //除数auto p = SmallDiv(sSub, sNum2, false);int nStart = sNum2.Length;//获取第一位,确保第一次 p.Fist不等于0if (p.First == 0) {sSub = sNum1.SubStr(0, sNum2.Length + 1);p = SmallDiv(sSub, sNum2, false);nStart = sNum2.Length + 1;}for( int i = nStart; i <=  sNum1.Length; ++i){if (p.First > 0) {//商不为0 sResult.Add(_tostr(p.First));if (p.Second == _t("0")) { //商不为0,余数为0sSub = sNum1.SubStr(i, 1);		}else{	 //商不为0,余数不为0sSub = p.Second + sNum1.SubStr(i, 1);	}if(sSub.Length > 0)p = SmallDiv(sSub, sNum2, false);}else {     //--------------------------------商为零sResult.Add(_t("0"));if (p.Second == _t("0")) { //--------------商为0,余数为0sSub = sNum1.SubStr(i, 1); }else {	//----------------------------商为0,余数不为0			sSub = p.Second + sNum1.SubStr(i, 1);}if (sSub.Length > 0)p = SmallDiv(sSub, sNum2, false);}		}return sResult;}

例子:


int main()
{for (int i = 1; i < 100; ++i){_string s = _Integer::Divide(_t("2024"), _tostr(i));std::wcout << _t("2024/") << i << _t("\t\t");std::wcout << s << "\t";std::wcout << 2024 / i << "\n";}_string s1 = "88888888888888888888888888888888888888888888888888888888";_string s2 = "44444444444444444444444444444444444444444444444444444444";_string s3 = "23";_pcn(s1);_pcn(s2);_pcn(s3);_pcn(_Integer::Divide(s1,s2));_pcn(_Integer::Divide(s1, s3));_string s4 = _Integer::Divide(s1, s3);_pcn(s4);_pcn(_Integer::Divide(s2,s4));_pcn(_Integer::Multiplication(s4, s3));return 0;}

执行结果:

这篇关于C++大整数的加减乘除的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/941345

相关文章

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提