完美笔试的最后一题,只写了个+,准备用+模拟*的,回来看网上的资料,发现自己写得不对,于是回来花写时间写了下,各种心得。
实现思路很简单,用数组实现,同时用一个len表示占用空间,由于加法和乘法都要求对齐,所以按照数字的逆序表示要方便些,若要输出的话逆向输出即可(在此复习了下ostream 和friend 语义)。数组是字符串的集合,要保持字符串的特有的' '结尾符。下面的代码不求完美,但求思路,所以用了固定数组,同时不支持负数形式。
加法的实现比较简单,有点类似于归并的代码,注意最后要更新len和末尾结束符。
乘法借用的是网上的思路,用了一个临时数组(注意大小,如何证明不会溢出?),这个数组的类型有讲究,刚开始我用的是char,结果算打印不对,debug printf后发现中间某些值成为了负数,于是果断改为unsigned char,后来又对很大的数相乘,测试结果与Windows自带Calc相比,发现中间某些位有些不一样,如下(上面程序,下面Calc):
1111103676526184449295339622
1111103676554600449295339622
于是想可能又是溢出问题,改成unsigned int类型后,得到与Calc一致的结果。
附上一个多小时的成果吧,批评指正。
BigInt
#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] = '