文章详情

Php文档 Php问答 行业资讯 Php论坛 Php手册 Php博客
  • 游戏榜单
  • 软件榜单
关闭导航
热搜榜
热门下载
热门标签
关闭搜索
php爱好者> php文档>大整数类的实现

大整数类的实现

时间：2010-12-25  来源：万户侯

      写这个大整数类有两个目的，第一是为了复习一下C++的基本思想，第二是今后若有项目可以用到则有基础。但是昨晚为了赶工，有些算法没有优化，类的设计也不是很合理，而且在代码编写过程中还是有一些问题困扰着我。下面将代码贴出，请各位走过路过的大牛提提建议，批评指正。

      大整数类BigInt使用字符串存储整数，如整数1000则保存为"1000"。

      头文件BigInt.h如下，其中自定义了一个异常类，用于防止使用非法字符串来初始化整数，如"1dfaf"等。 

/*******************************************
* 大整数类BigInt
* 功能：存储无限长整数
* 作者：万户侯(billsedison)
* 日期：2010.12.24
* 版本：1.0
*******************************************/
// BigInt.h
#ifndef _BIG_INT_
#define _BIG_INT_


// g++不通过，由于BigInt&与BigInt的区别，以后需要再研究
// 为何const BigInt&作为BigInt::IsLegal的参数会通不过编译？
// VC6，VS2010通过

#include <iostream>
#include <string>
#include <stdexcept>
#include <algorithm>
#include <fstream>

using namespace std; // 这里为了赶工，就在头文件里引入了命名空间std，以后需要做调整

// 自定义异常类，考虑BigInt是否合法
class bigint_error : public runtime_error
{
public:
        bigint_error(const string& msg = "") : runtime_error(msg)
        {
        }
};

// 定义负号
#define MINUS_SYMBOL '-'

// 定义宏，将字符转为对应的数字
#define CHAR_TO_INT(x) ((x) - 0x30)

// 定义宏，将对应的数字转为字符
#define INT_TO_CHAR(x) ((char)((x) + 0x30))

// VC6 bug
// 重载操作符需要在类外声明
class BigInt;
// 比较运算 >
bool operator > (BigInt& b1, BigInt& b2);
// 比较运算 >=
bool operator >= (BigInt& b1, BigInt& b2);
// 比较运算 <
bool operator < (BigInt& b1, BigInt& b2);
// 比较运算 <=
bool operator <= (BigInt& b1, BigInt& b2);
// 比较运算 ==
bool operator == (BigInt& b1, BigInt& b2);
// 比较运算 !=
bool operator != (BigInt& b1, BigInt& b2);
// 输出
ostream& operator << (ostream& os, BigInt& b);        
// 友元函数，大整数类加法
BigInt operator + (BigInt& b1, BigInt& b2);
// 友元函数，大整数类减法
BigInt operator - (BigInt& b1, BigInt& b2);
// 友元函数，大整数类乘法
BigInt operator * (BigInt& b1, BigInt& b2);
// 友元函数，大整数类除法
BigInt operator / (BigInt& b1, BigInt& b2);
// 友元函数，大整数类取余
BigInt operator % (BigInt& b1, BigInt& b2);

// 大整数类
class BigInt
{
private:
        string m_strInt; // 使用字符串来保存整数
        static const string m_cstrLegalChar; // 保存合法字符
public:
        // Constructor/Destructor
        // 构造函数
        BigInt(const string& str = "0"); // 初始化为0
        BigInt(const char* pstr); // 初始化为0
        // 拷贝构造函数
        BigInt(BigInt& b);
public:
        // getter/setter
        const string& GetStrInt()
        {
                return m_strInt;
        }
public:
        // Attributes
        // 判断大整数是否合法
        bool IsLegal(); 
        // 若为0，消除负号，否则返回原样
        BigInt& DelZeroNeg();
private:
        // 正数加法（纯正数加法，不考虑负号）
        BigInt Add(BigInt& b);
        // 正数减法（纯正数减法，不考虑负号）
        BigInt Sub(BigInt& b);
        // 正数乘法（纯正数乘法，不考虑负号）
        BigInt Mul(BigInt& b);
        // 正数除法（纯正数除法，不考虑负号）
        BigInt Div(BigInt& b);
        // 正数取余（纯正数取余，不考虑负号）
        BigInt Mod(BigInt& b);
        // 正数比较，返回值> 0 则>，< 0 则小, == 0则相等
        int Cmp(BigInt& b);
        // 是否为0，消除0与-0的差别
        bool IsZero();  
public:
        // 成员operator
        // 取负
        BigInt operator - ();
        // 赋值
        BigInt& operator = (BigInt& b);
        // 赋值
        BigInt& operator = (const string& b);
        // 自增
        BigInt& operator ++ ();
        // 自增，后置
        BigInt operator ++ (int);
        // 自减
        BigInt& operator -- ();
        // 自减，后置
        BigInt operator -- (int);
        // 赋值 +=
        BigInt& operator += (BigInt& b);
        // 赋值 -=
        BigInt& operator -= (BigInt& b);
        // 赋值 *=
        BigInt& operator *= (BigInt& b);
        // 赋值 /=
        BigInt& operator /= (BigInt& b);
        // 赋值 %=
        BigInt& operator %= (BigInt& b);
public:
        // 友元operator   
        // 比较运算 >
        friend bool operator > (BigInt& b1, BigInt& b2);
        // 比较运算 >=
        friend bool operator >= (BigInt& b1, BigInt& b2);
        // 比较运算 <
        friend bool operator < (BigInt& b1, BigInt& b2);
        // 比较运算 <=
        friend bool operator <= (BigInt& b1, BigInt& b2);
        // 比较运算 ==
        friend bool operator == (BigInt& b1, BigInt& b2);
        // 比较运算 !=
        friend bool operator != (BigInt& b1, BigInt& b2);
        // 输出
        friend ostream& operator << (ostream& os, BigInt& b); 
        // 友元函数，大整数类加法
        friend BigInt operator + (BigInt& b1, BigInt& b2);
        // 友元函数，大整数类减法
        friend BigInt operator - (BigInt& b1, BigInt& b2);
        // 友元函数，大整数类乘法
        friend BigInt operator * (BigInt& b1, BigInt& b2);
        // 友元函数，大整数类除法
        friend BigInt operator / (BigInt& b1, BigInt& b2);
        // 友元函数，大整数类取余
        friend BigInt operator % (BigInt& b1, BigInt& b2);
};

#endif

        头文件中，定义了大整数类的属性与方法，其中使用了大量运算符重载，使得BigInt的使用与一般整数如int的使用方法类似，下面给出类的实现文件代码BigInt.cpp，代码如下： 

// BigInt.cpp
#include "BigInt.h"

// 保存合法字符
const string BigInt::m_cstrLegalChar = "0123456789-";

// 构造函数
BigInt::BigInt(const string& str) : m_strInt(str)
{
        // 若为空字符串
        if (m_strInt.empty())
        {
                m_strInt = "0"; // 初始化为0
        }
        else // 不为空
        {
                if (!IsLegal()) // 如果不合法
                {
                        throw bigint_error("初始化含有非法字符");
                }
                DelZeroNeg();
        }
}

BigInt::BigInt(const char* pstr) :m_strInt(pstr)
{
        // 若为空字符串
        if (m_strInt.empty())
        {
                m_strInt = "0"; // 初始化为0
        }
        else // 不为空
        {
                if (!IsLegal()) // 如果不合法
                {
                        throw bigint_error("初始化含有非法字符");
                }
                DelZeroNeg();
        }
}

// 拷贝构造函数
BigInt::BigInt(BigInt& b)
{
        operator = (b);
}

// 判断大整数是否合法
bool BigInt::IsLegal()
{
        bool bRet;
        // 对于个位数
        if (m_strInt.length() == 1)
        {
                // 判断是否含有除负号之外的所有字符
                // 若找到其他字符，则返回false
                return !(m_strInt.find_first_not_of(m_cstrLegalChar.substr(0, m_cstrLegalChar.length() - 1)) != string::npos);
        }
        else // 对于多位数
        {
                bRet = true;
                // 判断第一位，可含符号位
                bRet &= (m_cstrLegalChar.find(m_strInt.at(0)) != string::npos);
                // 判断余下位数
                bRet &= !(m_strInt.substr(1).find_first_not_of(m_cstrLegalChar.substr(0, m_cstrLegalChar.length() - 1)) != string::npos);
                return bRet;
        }
}

// 正数加法（纯正数加法，不考虑负号）
BigInt BigInt::Add(BigInt& b)
{
        string strResult; // 保存结果的字符串
        int i = m_strInt.length() - 1, j = b.GetStrInt().length() - 1;
        int fstNum, sndNum; // 第一个，第二个个位数
        int sum; // 每一次加法的和
        int carry = 0; // 保存进位
        while (i >= 0 && j >= 0) // 从后往前加法
        {
                // 从后往前加法，将每一位转成对应的数字
                fstNum = CHAR_TO_INT(m_strInt.at(i));
                sndNum = CHAR_TO_INT(b.GetStrInt().at(j));
                sum = fstNum + sndNum + carry;          
                // 处理进位
                if (sum >= 10)
                {                       
                        carry = sum / 10;
                        sum %= 10;
                }
                else
                {                       
                        carry = 0;
                }
                strResult.append(string(1, INT_TO_CHAR(sum))); // 先顺序加
                i--;
                j--;
        }

        // 处理剩余部分               
        while (i >= 0)
        {
                if (carry != 0)
                {
                        sum = CHAR_TO_INT(m_strInt.at(i)) + carry;
                        // 处理进位
                        if (sum >= 10)
                        {                       
                                carry = sum / 10;
                                sum %= 10;
                        }
                        else
                        {                       
                                carry = 0;
                        }
                        strResult.append(string(1, INT_TO_CHAR(sum))); // 先顺序加
                }
                else
                {
                        strResult.append(string(1, m_strInt.at(i)));
                }
                i--;
        }

        
        while (j >= 0)
        {
                if (carry != 0)
                {
                        sum = CHAR_TO_INT(b.GetStrInt().at(j)) + carry;
                        // 处理进位
                        if (sum >= 10)
                        {                       
                                carry = sum / 10;
                                sum %= 10;
                        }
                        else
                        {                       
                                carry = 0;
                        }
                        strResult.append(string(1, INT_TO_CHAR(sum))); // 先顺序加
                }
                else
                {
                        strResult.append(string(1, b.GetStrInt().at(j)));
                }
                j--;
        }

        if (carry != 0) // 若此时进位还不为0
        {
                strResult.append(string(1, INT_TO_CHAR(carry))); // 先顺序加
        }

        // 反转结果
        reverse(strResult.begin(), strResult.end());
        return BigInt(strResult).DelZeroNeg();
}

// 正数减法（纯正数减法，不考虑负号）
BigInt BigInt::Sub(BigInt& b)
{
        int nCmp = Cmp(b);
        if (nCmp == 0) // 如果二者相等
        {
                return BigInt("0");
        }
        string strResult; // 保存结果的字符串
        int i = m_strInt.length() - 1, j = b.GetStrInt().length() - 1;
        int fstNum, sndNum; // 第一个，第二个个位数，第一个为较大数
        int diff; // 每一次减法的差
        int carry = 0; // 保存进位
        while (i >= 0 && j >= 0) // 从后往前减法
        {
                // 从后往前加法，将每一位转成对应的数字
                if (nCmp > 0)
                {
                        fstNum = CHAR_TO_INT(m_strInt.at(i));
                        sndNum = CHAR_TO_INT(b.GetStrInt().at(j));
                }
                else
                {
                        sndNum = CHAR_TO_INT(m_strInt.at(i));
                        fstNum = CHAR_TO_INT(b.GetStrInt().at(j));
                }
                
                diff = fstNum - sndNum - carry;         
                // 处理借位
                if (diff < 0)
                {                       
                        if (i != 0 || j != 0)
                        {
                                diff = 10 + diff;
                        }
                        carry = 1;
                }
                else
                {                       
                        carry = 0;
                }
                if (i == 0 && j == 0) // 最后一位
                {
                        if (diff > 0)
                        {
                                strResult.append(string(1, INT_TO_CHAR(diff))); // 先顺序加                         
                        }
                }
                else
                {
                        strResult.append(string(1, INT_TO_CHAR(diff))); // 先顺序加                         
                }
                i--;
                j--;
        }
        
        // 处理剩余部分
        if (nCmp > 0)
        {
                if (i >= 0)
                {
                        // 处理可能借位的最高位
                        diff = CHAR_TO_INT(m_strInt.at(i)) - carry;
                        if (diff > 0) // 防止将0插入
                        {
                                strResult.append(string(1, INT_TO_CHAR(diff))); // 先顺序加
                        }                       
                        i--;
                        while (i >= 0)
                        {                       
                                strResult.append(string(1, m_strInt.at(i)));
                                i--;
                        }
                }       
        }       
        else
        {
                if (j >= 0)
                {
                        // 处理可能借位的最高位
                        diff = CHAR_TO_INT(b.GetStrInt().at(j)) - carry;
                        if (diff > 0) // 防止将0插入
                        {
                                strResult.append(string(1, INT_TO_CHAR(diff))); // 先顺序加
                        }
                        j--;
                        while (j >= 0)
                        {
                                strResult.append(string(1, b.GetStrInt().at(j)));
                                j--;
                        }
                }               
        }
        
        // 反转结果
        reverse(strResult.begin(), strResult.end());
        return (nCmp > 0) ? BigInt(strResult).DelZeroNeg() : (-BigInt(strResult)).DelZeroNeg();
}

// 正数乘法（纯正数乘法，不考虑负号）
BigInt BigInt::Mul(BigInt& b)
{
        // 直接对0做处理
        if (*this == BigInt("0") || b == BigInt("0"))
        {
                return BigInt("0");
        }
        string strResult; // 保存结果的字符串
        int nLen = m_strInt.length() - 1, nbLen = b.GetStrInt().length() - 1;
        int carry = 0; // 保存乘法的进位
        int mul; // 保存乘法的结果
        int i, j;
        BigInt biResult;
        for (i = nbLen; i >= 0; i--)
        {
                strResult = ""; // 保存个位乘以b的值
                carry = 0;
                for (j = nLen; j >= 0; j--)
                {
                        mul = CHAR_TO_INT(m_strInt.at(j)) * CHAR_TO_INT(b.GetStrInt().at(i)) + carry;
                        if (mul < 10)
                        {
                                strResult.append(string(1, INT_TO_CHAR(mul)));
                                carry = 0;
                        }
                        else
                        {
                                while (mul >= 10)
                                {
                                        strResult.append(string(1, INT_TO_CHAR(mul % 10)));
                                        carry = mul /= 10;
                                }
                        }
                }
                // 最后所剩的高位
                if (carry != 0)
                {
                        strResult.append(string(1, INT_TO_CHAR(carry)));
                }               
                // 翻转成正常数位
                reverse(strResult.begin(), strResult.end());
                // 移位乘以10，即末尾补0
                strResult.append(string(nbLen - i, '0'));
                biResult = biResult.Add(BigInt(strResult)); // 将结果相加
        }
        
        return biResult.DelZeroNeg();
}

// 正数除法（纯正数除法，不考虑负号）
BigInt BigInt::Div(BigInt& b)
{
        // 检查除数是否为0
        if (b == BigInt("0"))
        {
                throw bigint_error("除数为0");
        }
        int nCmp = Cmp(b);
        if (nCmp == 0) // 若相等
        {
                return BigInt("1");
        }
        else
        {
                int cnt = 0;
                BigInt biTmp(*this);
                while (biTmp >= b)
                {
                        cnt++;
                        biTmp = biTmp - b;
                }
                char cTmp[100];
                itoa(cnt, cTmp, 10);
                return BigInt(cTmp).DelZeroNeg();
        }
}

// 正数取余（纯正数取余，不考虑负号）
BigInt BigInt::Mod(BigInt& b)
{
        return (*this - Div(b) * b).DelZeroNeg();
}

// 正数比较，返回值> 0 则>，< 0 则小, == 0则相等
int BigInt::Cmp(BigInt& b)
{
        int nLen = m_strInt.length();
        int nbLen = b.GetStrInt().length();
        if (nLen > nbLen)
        {
                return 1;
        }
        else if (nLen < nbLen)
        {
                return -1;
        }
        else
        {
                int i;
                for (i = 0; i < nLen; ++i) // 逐位比较，从高位开始比较
                {
                        if (m_strInt.at(i) > b.GetStrInt().at(i))
                        {
                                return 1;
                        }
                        else if (m_strInt.at(i) < b.GetStrInt().at(i))
                        {
                                return -1;
                        }
                }
        }
        return 0; // 相等
}

// 是否为0，消除0与-0的差别
bool BigInt::IsZero()
{
        if (m_strInt.length() > 2)
        {
                return false;
        }
        if (m_strInt.at(0) == '0' && m_strInt.length() == 1)
        {
                return true;
        }
        else if (m_strInt.at(0) == '-' && m_strInt.at(1) == '0' && m_strInt.length() == 2)
        {
                return true;
        }
        else
        {
                return false;
        }
}

// 若为0，消除负号，否则返回原样
BigInt& BigInt::DelZeroNeg()
{
        if (IsZero())
        {
                m_strInt = "0";
        }
        return *this;
}

// 取负
BigInt BigInt::operator - ()
{
        if (!IsLegal())
        {
                throw bigint_error("一元operator - 操作数含有非法字符");
        }
        BigInt b(*this);
        bool bNeg = false;
        if (b.m_strInt.at(0) == MINUS_SYMBOL)
        {
                bNeg = true;
        }
        // 若已经为负数
        if (bNeg)
        {
                b.m_strInt.erase(0, 1); // 删除负号（删除第一个字符）
        }
        else // 若为正数
        {
                b.m_strInt.insert(0, string(1, MINUS_SYMBOL)); // 插入负号
        }
        return b.DelZeroNeg();
}

// 赋值
BigInt& BigInt::operator = (BigInt& b)
{
        if (!b.IsLegal())
        {
                throw bigint_error("operator = 操作数含有非法字符");
        }
        m_strInt.assign(b.GetStrInt().begin(), b.GetStrInt().end());
        return *this;
}

// 赋值
BigInt& BigInt::operator = (const string& b)
{
        if (!BigInt(b).IsLegal())
        {
                throw bigint_error("operator = 操作数含有非法字符");
        }
        m_strInt.assign(b.begin(), b.end());
        return *this;
}

// 自增
BigInt& BigInt::operator ++ ()
{
        *this = *this + BigInt("1");
        return *this;
}
// 自增，后置
BigInt BigInt::operator ++ (int)
{
        BigInt b = *this;
        *this = *this + BigInt("1");
        return b;
}
// 自减
BigInt& BigInt::operator -- ()
{
        *this = *this - BigInt("1");
        return *this;
}
// 自减，后置
BigInt BigInt::operator -- (int)
{
        BigInt b = *this;
        *this = *this - BigInt("1");
        return b;
}

// 赋值 +=
BigInt& BigInt::operator += (BigInt& b)
{
        *this = *this + b;
        return *this;
}
// 赋值 -=
BigInt& BigInt::operator -= (BigInt& b)
{
        *this = *this - b;
        return *this;
}
// 赋值 *=
BigInt& BigInt::operator *= (BigInt& b)
{
        *this = *this * b;
        return *this;
}
// 赋值 /=
BigInt& BigInt::operator /= (BigInt& b)
{
        *this = *this / b;
        return *this;
}
// 赋值 %=
BigInt& BigInt::operator %= (BigInt& b)
{
        *this = *this % b;
        return *this;
}

// 比较运算 >
bool operator > (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator > 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator > 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        if (bB1Neg && !bB2Neg) // 如果b1负但b2正
        {
                return false; // b1 < b2
        }
        else if (!bB1Neg && bB2Neg) // 如果b1正但b2负
        {
                return true; // b1 > b2
        }
        else if (bB1Neg && bB2Neg) // b1与b2均负
        {               
                return (-b1).Cmp(-b2) < 0; // 若absB1 < absB2，则b1 > b2
        }
        else // b1与b2均为正
        {
                return b1.Cmp(b2) > 0; // b1 > b2
        }
}

// 比较运算 >=
bool operator >= (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator >= 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator >= 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        if (bB1Neg && !bB2Neg) // 如果b1负但b2正
        {
                return false; // b1 < b2
        }
        else if (!bB1Neg && bB2Neg) // 如果b1正但b2负
        {
                return true; // b1 > b2
        }
        else if (bB1Neg && bB2Neg) // b1与b2均负
        {               
                return (-b1).Cmp(-b2) <= 0; // 若absB1 <= absB2，则b1 >= b2
        }
        else // b1与b2均为正
        {
                return b1.Cmp(b2) >= 0; // b1 >= b2
        }
}

// 比较运算 <
bool operator < (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator < 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator < 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        if (bB1Neg && !bB2Neg) // 如果b1负但b2正
        {
                return true; // b1 < b2
        }
        else if (!bB1Neg && bB2Neg) // 如果b1正但b2负
        {
                return false; // b1 > b2
        }
        else if (bB1Neg && bB2Neg) // b1与b2均负
        {               
                return (-b1).Cmp(-b2) > 0; // 若absB1 > absB2，则b1 < b2
        }
        else // b1与b2均为正
        {
                return b1.Cmp(b2) < 0; // b1 < b2
        }
}
// 比较运算 <=
bool operator <= (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator <= 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator <= 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        if (bB1Neg && !bB2Neg) // 如果b1负但b2正
        {
                return true; // b1 < b2
        }
        else if (!bB1Neg && bB2Neg) // 如果b1正但b2负
        {
                return false; // b1 > b2
        }
        else if (bB1Neg && bB2Neg) // b1与b2均负
        {               
                return (-b1).Cmp(-b2) >= 0; // 若absB1 >= absB2，则b1 <= b2
        }
        else // b1与b2均为正
        {
                return b1.Cmp(b2) <= 0; // b1 <= b2
        }
}
// 比较运算 ==
bool operator == (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator == 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator == 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        if ((bB1Neg && !bB2Neg) || (!bB1Neg && bB2Neg)) // 如果b1负但b2正
        {
                return false; // b1 != b2
        }
        else if (bB1Neg && bB2Neg) // b1与b2均负
        {               
                return (-b1).Cmp(-b2) == 0; // 若absB1 == absB2，则b1 == b2
        }
        else // b1与b2均为正
        {
                return b1.Cmp(b2) == 0; // b1 == b2
        }
}
// 比较运算 !=
bool operator != (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator != 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator != 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        if ((bB1Neg && !bB2Neg) || (!bB1Neg && bB2Neg)) // 如果b1负但b2正
        {
                return true; // b1 != b2
        }
        else if (bB1Neg && bB2Neg) // b1与b2均负
        {               
                return (-b1).Cmp(-b2) != 0; // 若absB1 == absB2，则b1 == b2
        }
        else // b1与b2均为正
        {
                return b1.Cmp(b2) != 0; // b1 == b2
        }
}

// 输出
ostream& operator << (ostream& os, BigInt& b)
{
        if (!b.IsLegal())
        {
                throw bigint_error("operator << 操作数含有非法字符");
        }
        return os << b.GetStrInt();
}

// 友元函数，大整数类加法
BigInt operator + (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator + 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator + 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        // 如果都是负数
        if (bB1Neg && bB2Neg)
        {
                return (-((-b1).Add(-b2))).DelZeroNeg();
        }
        else if (!bB1Neg && !bB2Neg) // 都为正数
        {
                return (b1.Add(b2)).DelZeroNeg();
        }
        else if (bB1Neg && !bB2Neg) // b1为负，b2为正
        {
                return (b2.Sub(-b1)).DelZeroNeg();
        }
        else // b1为正，b2为负
        {
                return (b1.Sub(-b2)).DelZeroNeg();
        }
}

// 友元函数，大整数类乘法
BigInt operator - (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator - 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator - 第二个操作数含有非法字符");
        }
        return (b1 + (-b2)).DelZeroNeg();
}

// 友元函数，大整数类乘法
BigInt operator * (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator * 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator * 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        // 如果都是负数或都为正数
        if (!bB1Neg && !bB2Neg)
        {
                return (b1.Mul(b2)).DelZeroNeg();
        }
        else if (bB1Neg && bB2Neg)
        {
                return ((-b1).Mul(-b2)).DelZeroNeg();
        }
        else if (!bB1Neg && bB2Neg)     
        {
                return (-b1.Mul(-b2)).DelZeroNeg();
        }
        else
        {
                return (-b2.Mul(-b1)).DelZeroNeg();
        }
}

// 友元函数，大整数类除法
BigInt operator / (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator / 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator / 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        // 如果都是负数或都为正数
        if (!bB1Neg && !bB2Neg)
        {
                return (b1.Div(b2)).DelZeroNeg();
        }
        else if (bB1Neg && bB2Neg)
        {
                return ((-b1).Div(-b2)).DelZeroNeg();
        }
        else if (!bB1Neg && bB2Neg)     
        {
                return (-b1.Div(-b2)).DelZeroNeg();
        }
        else
        {
                return (-(-b1).Div(b2)).DelZeroNeg();
        }
}

// 友元函数，大整数类取余
BigInt operator % (BigInt& b1, BigInt& b2)
{
        // 判断b1, b2是否合法
        if (!b1.IsLegal())
        {
                throw bigint_error("operator % 第一个操作数含有非法字符");
        }
        if (!b2.IsLegal())
        {
                throw bigint_error("operator % 第二个操作数含有非法字符");
        }
        bool bB1Neg = false, bB2Neg = false; // 判断b1, b2的符号位（是否为负数）
        if (b1.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB1Neg = true;
        }
        if (b2.GetStrInt().at(0) == MINUS_SYMBOL) // 第一个操作数是否为负号
        {
                bB2Neg = true;
        }
        // 如果都是负数或都为正数
        if (!bB1Neg && !bB2Neg)
        {
                return (b1.Mod(b2)).DelZeroNeg();
        }
        else if (bB1Neg && bB2Neg)
        {
                return (-(-b1).Mod(-b2)).DelZeroNeg();
        }
        else if (!bB1Neg && bB2Neg)     
        {
                return (b1.Mod(-b2)).DelZeroNeg();
        }
        else
        {
                return (-(-b1).Mod(b2)).DelZeroNeg();
        }
}

但是其中有一个疑问如下：

倘若一个函数的签名为(const BigInt& b)，即常引用，在函数体内调用b.IsLegal()则会报错：vc1.cpp(29487) : error C2662: 'IsLegal' : cannot convert 'this' pointer from 'const class BigInt' to 'class BigInt &' Conversion loses qualifiers，可是我观察IsLegal函数的代码，发现似乎并没有去改动BigInt&本身的属性，这就造成我的困惑于不解，再将IsLegal的代码贴出如下： 

// 判断大整数是否合法
bool BigInt::IsLegal()
{
        bool bRet;
        // 对于个位数
        if (m_strInt.length() == 1)
        {
                // 判断是否含有除负号之外的所有字符
                // 若找到其他字符，则返回false
                return !(m_strInt.find_first_not_of(m_cstrLegalChar.substr(0, m_cstrLegalChar.length() - 1)) != string::npos);
        }
        else // 对于多位数
        {
                bRet = true;
                // 判断第一位，可含符号位
                bRet &= (m_cstrLegalChar.find(m_strInt.at(0)) != string::npos);
                // 判断余下位数
                bRet &= !(m_strInt.substr(1).find_first_not_of(m_cstrLegalChar.substr(0, m_cstrLegalChar.length() - 1)) != string::npos);
                return bRet;
        }
}

 希望走过路过的朋友们给予指出，谢谢。

最后给出测试代码，如求200的阶乘，代码如下： 

int main()
{
        try
        {
                // 示例，求阶乘
                BigInt fact = "1";
                BigInt index, num = "200";
                for (index = "2"; index <= num; ++index)
                {
                        fact *= index;
                }
                cout << num << "! = " << fact << endl;
        }
        catch (bigint_error& e)
        {
                cerr << e.what() << endl;
        }
        return 0;
}

结果输出为：

200! = 7886578673647905035523632139321850622951359776871732632947425332443594499
63403342920304284011984623904177212138919638830257642790242637105061926624952829
93111346285727076331723739698894392244562145166424025403329186413122742829485327
75242424075739032403212574055795686602260319041703240623517008587961789222227896
23703897374720000000000000000000000000000000000000000000000000

使用matlab对比，发现结果完全正确。（当然期间我已经做了大量的测试用例才能达到这种结果）

在平安夜，一个剩蛋，没有mm相伴，写下这些代码，希望能和园子里的朋友互相学习，这也是我第一篇随笔。*^_^*

相关阅读 更多 +
排行榜 更多 +
猎枪行动

猎枪行动

飞行射击 下载
导弹袭击

导弹袭击

飞行射击 下载
猫猫突围封锁要塞新手打法

猫猫突围封锁要塞新手打法

飞行射击 下载

Copyright 2006-2020 (phpxiu.com) All Rights Reserved.

本站为非盈利性网站，不接受任何广告。php爱好者