学步园

完美笔试的最后一题，只写了个+，准备用+模拟*的，回来看网上的资料，发现自己写得不对，于是回来花写时间写了下，各种心得。

实现思路很简单，用数组实现，同时用一个len表示占用空间，由于加法和乘法都要求对齐，所以按照数字的逆序表示要方便些，若要输出的话逆向输出即可（在此复习了下ostream 和friend 语义）。数组是字符串的集合，要保持字符串的特有的'\0'结尾符。下面的代码不求完美，但求思路，所以用了固定数组，同时不支持负数形式。

加法的实现比较简单，有点类似于归并的代码，注意最后要更新len和末尾结束符。

乘法借用的是网上的思路，用了一个临时数组（注意大小，如何证明不会溢出？），这个数组的类型有讲究，刚开始我用的是char，结果算打印不对，debug printf后发现中间某些值成为了负数，于是果断改为unsigned char，后来又对很大的数相乘，测试结果与Windows自带Calc相比，发现中间某些位有些不一样，如下（上面程序，下面Calc）：

1111103676526184449295339622
1111103676554600449295339622

于是想可能又是溢出问题，改成unsigned int类型后，得到与Calc一致的结果。

附上一个多小时的成果吧，批评指正。

#include <iostream>
#include <cstddef>
#include <cstdio>
#include <cstring>
using namespace std;

#define MAX 256 

class BigInt
{
public:
        BigInt(const char *str);
        BigInt(const BigInt &other);
        BigInt & operator =(const BigInt &other);
        BigInt & operator *=(const BigInt &other);
        BigInt & operator +=(const BigInt &other);


        friend ostream& operator<<(ostream&, const BigInt&);
private:
void MemSwap(BigInt &other)
        {
//std::iter_swap(vt,other.vt);
        }
private:
char vt[MAX];
        size_t len;
};

BigInt::BigInt(const char *str)
{
char *ptr = const_cast<char *>(str);
    len = strlen(str); 
//strcpy(vt,str);
    size_t i = len;
//逆向拷贝
    while(*ptr)
        vt[--i] = *ptr++;
    vt[len] = '\0';

}

BigInt::BigInt(const BigInt &other):len(other.len)
{
    strcpy(vt,other.vt);    
}
BigInt & BigInt::operator = (const BigInt &other)
{
if(this == &other)
return *this;
//BigInt tmp(other);
    len = other.len;
    strcpy(vt,other.vt);

return *this;
}
BigInt & BigInt::operator +=(const BigInt &other)
{
    size_t i = 0;
    unsigned int sum;
int carrier = 0;
while((i < len) && (i < other.len))
    {
        sum = carrier + vt[i]+other.vt[i]-0x60;    
        vt[i]= sum % 10 + 0x30;//'0' = 0x30
        carrier = sum / 10;

        ++i;
    }
while(i < len)//other较短
    {
        sum = carrier + vt[i]-0x30;    
        vt[i]= sum % 10 + 0x30;
        carrier = sum / 10;

        ++i;
    }
while(i < other.len)//other较长
    {
        sum = carrier + other.vt[i]- 0x30;    
        vt[i]= sum % 10 + 0x30;
        carrier = sum / 10;

        ++i;
    }
if(carrier)
        vt[i++] = '1';
    vt[i]='\0';
//更新len的长度
    len = i;
return *this;
}
BigInt & BigInt::operator *= (const BigInt &other)
{
    size_t i = 0;
    size_t total = len + other.len;

//unsigned char *tmpVt = new unsigned char[total + 1];
    unsigned int *tmpVt = new unsigned int[total + 1];
    memset(tmpVt,0,sizeof(int)*(total+1));
for(size_t i = 0 ; i < other.len; ++i)
for(size_t j = 0; j < len ; ++j)
        {
//
            tmpVt[i+j] += (other.vt[i]-'0')*(vt[j]-'0');
            printf("i = %d\tj = %d\t i+j = %d\n",i,j,tmpVt[i+j]);
        }
//实现进位,一直到[i+j]都有值
    for(size_t i = 0; i < total; ++i)
if(tmpVt[i]>=10)//大于10
        {
            tmpVt[i+1]+= tmpVt[i]/10;
            tmpVt[i]=tmpVt[i]%10;
            printf("i = %d\ttmpVt[i] = %d\n",i,tmpVt[i]);
        }
for(size_t i = 0; i < total; ++i)
        vt[i] = tmpVt[i] + '0';


    delete []tmpVt;
//更新len的值，并保持字符串的
    len = total;
    vt[len]='\0';
return *this;
}
ostream& operator<<(ostream& os, const BigInt& val)
{
    size_t i = val.len;
while(i != 0 )
        os << val.vt[--i];
    os<<'\n';
}

int main()
{
    BigInt a("111111111111111111100");
    BigInt b("988800003234");
    BigInt c("9999933");
    a += b;
    cout<<a;

    a *= c;
    cout <<a;

return 0;
}