两个大数相减

最近，在网上看到一篇讲大数相减的文章，讲的思想是对的，但是代码编写不正确，就对其进行了改正。

参考文章链接：http://www.cnblogs.com/ballwql/archive/2013/04/20/3032090.html

大数相减与大数相加相比，需要考虑借位问题。处理借位需要考虑二种情况，假设被减数为Sub1，减数为Sub2，这些都是以字符串形式存储的大数。则大致要考虑二种情况的借位：?

?1)Length of Sub1 is greater or equal to Length of Sub2: 此时需要考虑两种借位：一种是Sub1大数大于Sub2大数，则Sub1最高位（Sub1首位置）无需再进一步借位，此种状况比较好处理；另一种是Sub1大数小于Sub2大数，则Sub1最高位还需进一步借位，此种情况处理稍微复杂，在下面将展开讨论.

2）Length of Sub1 isless than Length of Sub2: 此种情况即Sub1最高位还需进一步借位情况，我们在此假设Sub1长度不足Sub2长度的部分填充0，以"123"(sub1) -"456789"(sub2)为例，如下简图所示，最终结果应该为"456666",还要加负号表示结果为负数。在此过程中还要引入一个基数作为调整，基数设定原理是以第一种情况所算出的最终值为参考，如下图参考基数所述，其实只要理解相减过程，此步不难理解。

/**
* 大数相减，但这两个大数是正整数
* 暂时没有考虑有负数的情况和其他非法输入的情况
* 
*/

#include <iostream>
#include <string.h>
using namespace std;
const int N=1002;

void Sub(char *p1,char *p2,int *p3)
{
    int i,j,k=0;
    
    int bit=0,t=0; //bit：表示借位，1：表示需要借位，0：表示不需要借位。t：存储中间计算的位相减值
    int len1=strlen(p1);  //被减数的长度
    int len2=strlen(p2); //减数的长度
	bool isBeginning0 = true;
    
    for(i=len1-1,j=len2-1;i>=0 && j>=0;--i,--j) //此为循环遍历两数，分别对位进行相减操作
    {
        t=(p1[i]-'0')-(p2[j]-'0')-bit;    //计算两个位之间的差值，同时要考虑借位
        
        if(t<0)  //如果t小于0，表示需要借位，bit赋值为1，且最终相减结果需加10作为调整并存储到p3数组中，自己用笔画一下就好理解.
        {
			bit=1;
			//例：123-456，t相减实际值分别为-3(3-6-0(bit))，-4（2-5-1(bit))，-4（1-4-1(bit)),加10调整后为：
			// 7,6,由于最高位相减后还bit为1即还需借位，  因此还需调整,转换为第一种情况，即用1000-667=333，且结果为负    
            p3[k++]=t+10;        
        }
        else
        {
            bit=0; //相减为正，则无需调整，直接将t赋给p3对应位。
            p3[k++]=t;
        }   
    }

	//strlen(p1)>strlen(p2),result is greater than zero
    while(i>=0) 
    {
        t=p1[i]-'0'-bit;
        if(t<0)
        {
            bit=1;
            p3[k++]=t+10;
        }
        else
        {
            bit=0;
            p3[k++]=t;
        }
        i--;
    }

	//strlen(p1)<strlen(p2),result is less than zero
    while(j>=0) 
    {
     
		t = 0 - (p2[j]-'0') - bit;
		if(t<0)
		{
			bit = 1;
			p3[k++] = t + 10;
		}
		else
		{
			bit = 0;
			p3[k++] = t;
		}
		j--;
    }

	//对仍有进位的情况考虑，主要分两种：
	//一种是strlen(p1)==strlen(p2),但p1<p2
	//另一种是strlen(p1)<strlen(p2)，p1<p2
	//这两种情况都是bit为1
	//但要注意1点：从低位到高位求减法时，要从不为0的位开始减
    if(bit==1)  
    {
		for(j = 0; j < k; ++j)
			if(p3[j] != 0)
				break;

        p3[j]=10-p3[j];
        for(i=j+1;i<k;++i)
        {
            p3[i]=10-p3[i]-bit;
        }        
    }

    if(bit==1)
        cout<<"-";

	//数字前面的0不输出，如-09，输出-9
    for(i=k-1;i>=0;--i)
	{
		if(isBeginning0 && p3[i] != 0)
			isBeginning0 = false;
		if(!isBeginning0)
			cout<<p3[i];
	}
    cout<<endl;
}

int main()
{
    char c1[N],c2[N];
    int a[N];
    int i,j;

    while(cin>>c1>>c2)
    {
        memset(a,sizeof(a));
        Sub(c1,c2,a);
    }

    return 0;
}