鉴于从本篇文章开始后的高精度运算类加入了“负数”概念,在实现高精度整数运算的时候如果要求能计算负数,那就需要在每次运算的时候加入很多判断,这在解题过程中会使效率降低很多,所以我将本篇文章及之后相关的文章都归类到“开发探索”当中。实际上,在比赛中如果需要用到负数,只要知道负数的下界,我们就可以用正整数来表示负数,方法为:

运算中处理的数字 = 实际数字 + 负数下界的绝对值

通过这样的方法我们可以规避对于负数运算的额外判断,而且可以确保在运算过程中只会涉及到正整数间的运算,而绝不会出现负数。
但是对于一个真正的高精度运算而言,存在下界是不允许的,所以在这里,我们就来探讨整个整数域上的高精度运算。
在高精度整数类中,我们增加一个成员symbol来表示当前数字的符号是正或是负。这样我们在运算的时候就可以针对数字的符号来选择进行何种方式的运算。需要关注的是,我们要处理的是正整数,数字的符号是作为一种标记来存在的,所以现在我先将正负数字之间存在的各种运算关系整理如下,使我们在运算过程中只考虑正数与正数的运算

正数 + 正数 = 正数 + 正数
负数 + 正数 = 正数 – (-负数)
正数 + 负数 = 正数 – (-负数)
负数 + 负数 = -((-负数) + (-负数))

关于正负数之间的减法,我们是这样规定的:
基本的规则是:

绝对值较大的数字 – 绝对值较小的数字

也就是所有涉及负数的运算,都要符合这个规则,如果一个较小数字去减较大数字,那么则交换这两个数字,最后的结果符号改变一下即可。

正数 – 负数 = 正数 + (-负数)
正数 – 正数 = 正数 – 正数
负数 – 正数 = -((-负数) + 正数)
负数 – 负数 = -((-负数) – (-负数))

这样,我们就把各种情况考虑到了,在涉及到运算的过程中,我们只要考虑正数和正数的运算即可了。
其中“-”运算符单独和数字一起使用的时候作为负号,只改变数字的符号标记,对其值不做任何改变(对数字0的处理除外)。在C++当中,只需要将“-”进行单目运算符的重载即可实现。
至于减法的实现,和之前加法的实现类似,只不过“进位”要改为“借位”,稍微有点区别,但是实现起来并不困难。
在引入负数之后,乘法以及比较的算法也需要做出一些调整,乘法比较简单:

因数符号相同 = 正数
因数符号不同 = 负数

而对于比较而言,增加的部分需要,遵循下面的规则:

正数 > 负数
负数 ? 负数 = 绝对值大的数字小

和上面的运算类似,这样做,是为了让我们在对数字进行操作的时候,仅仅考虑数字本身,而不考虑符号。
截止到目前的高精度运算类的代码附于下面,我对其中涉及本篇文章内容的代码进行高亮处理,方便阅读:

说点什么

2 评论 在 "高精度整数运算(5)负数与减法"

提醒
排序:   最新 | 最旧 | 得票最多
刚才的代码粘过来的时候关键字竟然都去掉了 // // bign.h // Bign // // Created by shanker wang on 12-11-1. // Created by Xc… 阅读更多 »
如果固定高精度整数的长度,做加减法的时候舍去溢出位,也可以表示负数。让最高位大于等于5的看作是负数,小于5的看作是正数,就可以得到一种类似于补码表示法的一种表示负数的方法。优点是算法简洁,不用判断正负… 阅读更多 »