高精度整数运算(7)模运算&总结

取模(Mod)运算应当是我们这个高精度运算类的最后一种运算了^ ^,长达一周的高精度整数运算的介绍的尾声也即将到来~后面部分我将重点介绍模运算,并对高精度整数运算类的最终成品做一点总结。 那么模运算究竟是什么呢?按照大家通俗的理解就是除法运算中剩下的尾巴——余数。其实却实可以这样理解,首先,我们来明确一下除法的表达: A / B = [A / B] + R / B []运算代表向下取整,比如[1.6] = 1。那么[A / B]实际上就是我们做除法运算后所得到的“商”(其实如果商为负数的话,这样说是不合适的,我会在下文中具体解释),而R / B则是除法运算后面的浮点数部分(假如以后有机会做高精度浮点数的运算的话,用这个式子来求是很方便的哦~)。R则是我们这次的主角——模值。 经过整理,我们就可以得到取模运算在数学上的定义: R = A – [A / B] * B 上面这个公式中所有的运算我们之前都已经完成过了,哈哈,看来代码也就是一行的事呀,可是,一次除法运算、一次乘法运算、一次减法运算……这三

高精度整数运算(6)除法

除法是我们实现高精度整数运算中的最后一个四则运算,之所以会放到如此靠后的位置,那是因为在我看来,除法是这四个运算里最难实现的。实际上,在实现除法的运算中,我们用到了几乎之前所有的内容,包含“比较”、“乘法”、“减法”。所以在有了前面的铺垫后,我们实现高精度整数的除法运算就轻而易举了。 依照惯常思路,我们利用我们手算除法的方式来实现高精度除法运算,如图1所示。 我们从左侧逐位获取被除数的一位,然后进行试除,并记录商,反复操作后就能得到高精度商,这个商是向下取整的(没有浮点位),在除法运算的试除的过程中,我们把除数从9开始作为商进行试除,试除的商递减,第一个使得被除数相同位数字减去试除商乘以除数的结果大于零的试除商,即为实际此位上的商。 最后只需要把前导零去除,并按照乘法处理数字符号的方法给结果填上正负标记即可(除法和乘法可以相互转化,但是在运算中我们没有这么做的原因是,除数求倒的过程需要高精度的浮点数,而且该浮点数很可能是无限循环的,这会导致我们的结果最后并不准确)。 下面就是除法的具体实...

高精度整数运算(5)负数与减法

鉴于从本篇文章开始后的高精度运算类加入了“负数”概念,在实现高精度整数运算的时候如果要求能计算负数,那就需要在每次运算的时候加入很多判断,这在解题过程中会使效率降低很多,所以我将本篇文章及之后相关的文章都归类到“开发探索”当中。实际上,在比赛中如果需要用到负数,只要知道负数的下界,我们就可以用正整数来表示负数,方法为: 运算中处理的数字 = 实际数字 + 负数下界的绝对值 通过这样的方法我们可以规避对于负数运算的额外判断,而且可以确保在运算过程中只会涉及到正整数间的运算,而绝不会出现负数。 但是对于一个真正的高精度运算而言,存在下界是不允许的,所以在这里,我们就来探讨整个整数域上的高精度运算。 在高精度整数类中,我们增加一个成员symbol来表示当前数字的符号是正或是负。这样我们在运算的时候就可以针对数字的符号来选择进行何种方式的运算。需要关注的是,我们要处理的是正整数,数字的符号是作为一种标记来存在的,所以现在我先将正负数字之间存在的各种运算关系整理如下,使我们在运算过程中只考虑正数与正数的运算:

高精度运算(4)比较

比较运算用于比较两个高精度整数的大小,算法十分简单,只需要按照两个规则,就可以得到两个数字谁大谁小: (1)如果一个数字比另一个数字位数少,则这个数字必比另一个数字小。 这就要求我们存储的数字不能有前导零。 (2)从末位开始向个位逐个比较,位上的数字大的,则这个数字也大。 通过这样的比较法则,我们就可以实现比较运算小于号“<”: [crayon-59c2156913b58853810991/] 神奇的是,我们只需要一个小于的比较运算符,就可以实现其它所有的比较运算符,请看下面的代码: [crayon-59c2156913b5d095715503/] 下面给出完整的高精度运算类的代码: [crayon-59c2156913b5f979477819/]

高精度运算(3)乘法

在本篇文章中我们将实现高精度乘法运算。 乘法和加法比起来就复杂很多了,我们知道乘法可以由加法直接实现(连续加因数2次因数1),在有我们之前的加法运算的基础的情况下,这种乘法运算极其简单便能实现(但是需要先做出高精度数比较运算,这是下节的内容了,不过这种方法并不明智,对于一个N位数乘以N位数的运算,其时间复杂度为O(10^N),这个增长速度实在是太大了。 那么我们继续按照上次的思路,回到我们算乘法的竖式,看图1: 对于我们的乘法运算,按照计算机的运算思路,就是两个大循环,逐位相乘,最后再相加,然后转换为十进制数字,也就是进位,就能得到我们的结果了。 下面是乘法的实现方法: [crayon-59c2156913d33303323307/] 依照惯例,给出完整的高精度整数类的代码,除了增加了乘法及乘法相关的运算符的重载外,为了防止乘法运算中相加过程中出现数值溢出,原先的short类型的容器修改为了int,这样可以确保不会出现乘法运算溢出的现象,同时在每次赋值和输入的最后,会自动去掉数字的前...

高精度运算(2)加法

在解决了高精度整数的输入、存储以及输出的问题后,我们终于开始正式思考“运算”部分的实现。 加法是最简单的一种四则运算,也是我们小学时数学最先就学到的运算规则,对于内置的整数类型而言,计算机通过二进制的电位运算可以快速的得到结果,而对于我们按位存入的高精度整数而言,要想对其进行加法运算,我们就需要返璞归真,首先,我们来回忆下小学时的加法,看图1: 从个位开始相加,结果放在横线下,如果相加的结果超过10,则进1到下一位。 没错,我们就是要所要依靠的就是这样一个简单的规则! 首先考虑到我们存储数字的方式:如果两个数字位数不同,则会出现超过数位的数字再相加时vector out of range的情况,所以我们要把两个数字一个一个加到结果的位置上(比如图1的个位,结果位原先是0,先把4加到结果位,结果位变为4,然后再把2加到结果为,变为6),这样可以方便我们对两个加数的各个位的情况进行把握。 下面就是加法运算的具体实现方法: [crayon-59c21569140e8459400427/...

高精度运算(1)结构

在解题过程中,经常会出现需要运算的数据超过系统内置的整型范围的情况,在这种时候我们就需要用到高精度运算算法,我将分几篇文章来解释,如何实现高精度运算,并且我将会将高精度运算封装为一个命名为BigInt的高精度整数类,方便未来的使用。 在本篇中,主要实现的是高精度整数的存储、输入与输出。 在给出具体的实现之前,我先介绍一点预备知识,关于C++标准库vector。 vector这个词在上一篇文章中提及过,vector是C++提供的一种顺序容器,而对于vector这种容器来说,其特点就是支持快速的随机访问(想一想数组通过下标值访问的方式),作为一种可变长的容器,我们可以把它当作一种“高端的数组”,用vector来存储高精度整数的好处在于可以解决由大整型数组来存数高精度整数时所造成的空间浪费问题。 我们对于高精度整数的存储方式是按位存储,为了避免运算的时候对齐各个位时产生麻烦,所以我们从个位开始存储,也就是说,在vector容器中存储的数字顺序,与你实际看到的数字顺序是正好相反的。 下面就给出具体