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

相关文章

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(

C++变换迭代器使用方法小结

《C++变换迭代器使用方法小结》本文主要介绍了C++变换迭代器使用方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、源码2、代码解析代码解析:transform_iterator1. transform_iterat