大整数-减法

---

问题描述

本文主要给出大数减法的一般思路。关于大数的一般性阐述可以参看大整数-加法-demo这篇博客。

思路

基本来说，还是大整数的那套思路。 要进行处理的数字，超过了计算机语言所能提供类型的最大范围。只能自己写数组存储每一位数字。由于不是内置类型，所以没有相应操作的支持。只能自己写，人工模拟减法操作。

加法主要是：从低位到高位，逐位相加，超过10的部分要”进位”减法主要是：从低位到高位，逐位相减，不够减的部分要”借位”

当然，具体写的时候，减法和加法还是有一些区别。下面这些点需要注意：

首先，减法需要判断大小。只能是大数 - 小数的时候才能用上面的规则，也就是说对于 2 - 8这种类型应该先计算 8 - 2 = 6， 然后再加上负号，得到-6。其次，输出的时候存在前导0的情形。用string实现，加法不存在前导0的情形，直接依次输出就行。减法输出的时候，不行。可能存在前导0的原因是因为，减法如果不减到最高位，你是不知道之前的这些0是前导0还是中间的0.只要最高位计算完毕之后你才知道。 我在写的时候由于是用string类型来存储大整数，所以在比较两个数大小的时候相对简单一点。如果数位相同的时候可以直接比较。但是，我之前忽略了一点就是，当数位不相同的时候，这种情形也是需要考虑的。比如66 - 8。如果直接用字符串比较，肯定会得到错误的结果。

代码

/* input: 多组输入数据; 字符串组织; process: 1.读入a,b; 2.判断：如果 a < b， 交换a与b的值 3.计算a_sz, c = 0; 3.循环：i < a_sz 3.1.先累加：left = a[i] + c; 3.2.判断：i < b_sz 3.2.1.true, right = b[i] 3.2.2.false, right = 0; 3.3.判断：left >= right 3.3.1.true,够减，计算当前位 left - right; c = 0; 3.3.2.flase, 不够减，计算当前位 left + 10 - right; c = - 1; 4.返回ret output: 测试数据： 66 9 1 2 88 5 2 999999999999 456786798787 4564564857921456645789789 */ #include <iostream> #include <string> #include <fstream> #define LOCAL std::string bign_minus( const std::string& a, const std::string& b ); int main( void ) { #ifdef LOCAL std::ifstream cin; cin.open( "input.dat" ); #endif std::string a, b; while( cin >> a >> b ) { bool flag = true; if( a.size() < b.size() || (a.size() == b.size() && a < b) ) { std::string tmp = a; a = b; b = tmp; flag = false; } std::string ret = bign_minus( std::string(a.rbegin(), a.rend()), std::string(b.rbegin(), b.rend()) ); int sz = ret.size(); int i = 0; for( i = sz - 1; ret[i] == '0'; --i ); if(!flag) std::cout << '-'; for( int j = i; j >= 0; --j ) std::cout << ret[j]; std::cout << std::endl; } #ifdef LOCAL cin.close(); #endif return 0; } std::string bign_minus( const std::string& a, const std::string& b ) { std::string ret; int a_sz = a.size(); int b_sz = b.size(); int c = 0; for( int i = 0; i < a_sz; ++i ) { int left = c + a[i] - '0'; int right = (i < b_sz)?(b[i] - '0'):0; if( left >= right ) { ret.push_back( '0' + left - right ); c = 0; } else { ret.push_back( '0' + 10 + left - right ); c = -1; } } return ret; }

注意

减法的特性：借位注意上述算法只能是”大-小”，如果遇见”小-大”的情形，先需要交换，然后进行计算，最后再添加负号。负号容易忘了输出的前导0要处理

---