0

C++大整数运算系列文章在前五节讲述了实现一个无符号大整数类的基本方法,而在实际应用中,通常还会有用到负数的情况。由于我们之前已经实现了无符号大整数类,重新再设计一个带符号大整数类无疑会做很多类似的且没有必要的工作。本文将介绍如何使用之前完成的无符号大整数类实现一个带符号大整数类。

目录

为了行文方便,我们假定无符号大整数类为ubigint,带符号大整数类为bigint。在计算机中,带符号数一般采用二进制补码或反码的方式实现,而对于大整数来说,我们可以认为它是一个无限长的数,因此其没有对应的补码或反码。我们可以认为一个带符号数是由一个无符号数和一个符号位表示的。 例如:

class bigint {
private:
    ubigint ubig;
    bool sign;
};

在signed int中,一般最高位为0表示正数,最高位为1表示负数,我们继承这样的传统,使sign为0(false)时表示正数,sign为1(true)时表示负数。这样就会使得数0有两种表示,即+0和-0,显然这有点不合理,于是我们规定数0只能表示为+0(即使0不是一个正数)。 讨论完带符号数的表示,下面介绍该如何实现四则运算。

加法

与无符号数的加法不同,带符号数的加法需要考虑更多的问题。两个同号的数相加,就是其ubig相加,sign不变;而两个异号的数相加则麻烦一些,由于无符号数只能用大数减小数,因此首先需要比较两个数绝对值的大小,然后再分类讨论。

假设两个带符号数为a和b,若a.ubig > b.ubig,当a为正数而b为负数时,a + b的结果即为a.ubig – b.ubig;当a为负数而b为正数时,a + b的结果即为 -(a.ubig – b.ubig)。

若a.ubig < b.ubig,当a为正数而b为负数时,a + b的结果即为 -(b.ubig – a.ubig); 当a为负数而b为正数时,a + b 的结果即为 b.ubig – a.ubig。 用代码表示如下:

bigint add(bigint a, bigint b)
{
    bigint result;
    if(a.sign == b.sign)
    {
        result.sign = a.sign;
        result.ubig = a.ubig + b.ubig;
    }
    else if(a.sign != b.sign)
    {
        if(a.ubig > b.ubig)
        {
            result.sign = a.sign;
            result.ubig = a.ubig - b.ubig;
        }
        else if(a.ubig < b.ubig)
        {
            result.sign = !a.sign;
            result.ubig = b.ubig - a.ubig;
        }
        else
        {
            result.sign = 0;
            result.ubig = ubigint(0);
        }
    }
    return result;
}

减法

在无符号整数中我们介绍了相应的减法操作,且在不够减的情况下还应该进行特殊处理。而在带符号数中,减法则简单的多,因为 a – b 相当于 a + (-b), 而在带符号数中,取相反数显然是一个简单的操作。 由于之前良好地实现了加法操作,这里的减法操作则可以忽略不提。

乘法

相比于加法来说,乘法则简单的多。假设两个乘数分别为a 和b。

若a和b符号相同,则结果为a.ubig * b.ubig;若a和b符号不同,则结果为-(a.ubig * b.ubig)。注意处理好数0的表示问题即可。 用代码表示如下:

bigint multi(bigint a, bigint b)
{
    bigint result;
    if(a == 0 || b == 0) result = bigint(0);
    else if(a.sign == b.sign)
        result.sign = 0, result.ubig = a.ubig * b.ubig;
    else result.sign = 1, result.ubig = a.ubig * b.ubig;
    return result;
}

除法

除法处理起来比乘法稍微复杂一些,因为除法不能只表示成两个绝对值的商。假设被除数和除数分别为a和b。

若a和b符号相同,显然结果为a.ubig / b.ubig。

当a和b符号不同时,假设商为c,余数为d,则a = b * c + d,且d的取值范围为:b>0 [0, b);b<0 (-b, 0]。 当d为0时,a整除b,商为-(a.ubig / b.ubig);当d不为0时,商为-(a.ubig / b.ubig + 1)。 如果读者难以理解为什么加一,可以考虑以下事实帮助理解:

-11 / 7  = -2 ... 3
11  / -7 = -2 ... -3
11  / 7  =  1 ... 4

至此,带符号大整数四则运算已经介绍完了,限于篇幅可能忽略了一些细节,有需要的读者可以到这里查看完整代码

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注