C++ 超大整数数学运算
数据结构、算法与应用 习题6.1 69题 p143
给出一种整数表示法，用于对任意大小的整数进行数学运算(加减乘除),且不能有精度损失。
这里应该能支持两种表示法，1链表，2数组。
使用链表比较符合我们直观上对于数字的印象，其中将 rear链接到最后一位数，那么使用prev就可以陆续的取出每一个数字。 并且在进行数学运算时，我们无需关注最终的位数，只需要将结果insert进入结果链表中即可。
由于没有规定一定是正整数，所以需要给一个符号。 （在网上也搜索了一些大数运算的参考，没有提供有符号运算的版本） 带符号的时候，逻辑会变复杂不少。
这里我给出一个带符号的方式 其中isNegative true为负数，false为正数
为了表示符号对于运算的影响，我会写两个版本的 加法
链表表示:
class BigInt: public Chain<int>{
public:
bool isNegative = false;
BigInt( int* a, int size ){ // 基于数组构造
for( int i=0; i<size; i++ ){
insert( a[i] );
}
}
// 最基本的 正正 相加
BigInt& operator+( BigInt& bigInt ){
int plus = 0; // 进位
int res = 0; // 单次计算结果
BigInt result = new BigInt; // 结果
ChainNode<int>* cursor = last();
ChainNode<int>* targetCursor = bigInt.last();
// 使用倒序的方式取出元素并计算
while( cursor->prev() && targetCursor->prev() ){
res = cursor->element + targetCursor->element + plus;
plus = res > 9 ? 1 : 0;
result->prepend( res ); // prepend即为 addAfter( head )
cursor = cursor->prev();
targetCursor = targetCursor->prev();
}
while( cursor->prev() ){
result->prepend( cursor->element );
cursor = cursor->prev();
}
while( targetCursor->prev() ){
result->prepend( targetCursor->element );
targetCursor = targetCursor->prev();
}
return result;
}
// 完整版 带符号运算的加法 （不是重载!!!）
BigInt& operator+( BigInt& bigInt ){
BigInt result = new BigInt; // 结果
result.isNegative = size() >= bigInt.size() ? isNegative : bigInt.isNegative; // 暂定为较大位数。 如果位数相同，根据最后一次计算结果修正。
int plus = 0; // 进位或借位
int res; // 单次计算结果
ChainNode<int>* cursor = last(); // 当前游标
ChainNode<int>* targetCursor = bigInt.last(); // 目标游标
while( cursor->prev() && targetCursor->prev() ){
res = isNegative ? -cursor->element : cursor->element
+ bigInt.isNegative ? -targetCursor->element : targetCursor->element
+ plus; // 我们把大数中的每一个数 都当成 a[i] * 10i来看。
// 绝对值超过>9的都需要向上进一位(一定是同符号)
// 不同符号 结果小于0的 需要借位
// 同符号小于0，不同符号大于0小于10的都可以忽略
// 小于0的时候 res需要取绝对值，保持元素的非负
if( res >9 || res<-9 ){
plus = 1;
}else if( res < 0 ){
plus = isNegative == bigInt.isNegative ? 0 : -1;
res = -res;
}
result.prepend(res);
}
if( size() == bigInt.size() ){ // 修复位数相同的问题
if( plus>0 ){
result.prepend(1); // 一定是同符号的，直接+1
}else if( plus<0 ){
result.isNegative = true; // 此时已经无法借位了，确认最终结果为负数
}
}
// 任意链表仍有元素未计算，继续补齐
while( cursor->prev() ){
result->prepend( cursor->element + plus );
plus = 0;
cursor = cursor->prev();
}
while( targetCursor->prev() ){
result->prepend( targetCursor->element + plus );
plus = 0;
targetCursor = targetCursor->prev();
}
// 修复首位为0的情况 // 全部删除则为空 即0
while( result.first().element == 0 ){
result.remove( result.first() );
}
return result;
}
// 在有符号加法的前提下，减法运算就简单多了
BigInt& operator-( BigInt& bigInt ){
bigInt.isNegative = !bigInt.isNegative; // 符号位颠倒
BigInt result = *this + bigInt;
bigInt.isNegative = !bigInt.isNegative; // 恢复
return result;
}
}
最近回复