电脑程序在进行整数数值计算的时候,会受到变量类型的内存空间使用大小而有数值表示范围的限制,所以当遇到过长的数值时,就无法正常地运算出结果。

以一个 8 比特的整数来说,它最多可以表示 28 种不同的整数。如果是无号整数的话,数值表示范围就是 0 ~ 255,如果是有号整数的话,数值表示范围就是 -128 ~ 127。以一个 16 比特的整数来说,它最多可以表示 216 种不同的整数,如果是无号整数的话,数值表示范围就是 0 ~ 65535;如果是有号整数的话,数值表示范围就是 -32768 ~ 32767。依此类推,有的编程语言(例如 Java)内置的基本整数类型最大是 64 比特,而有的编程语言(例如 Rust)内置的基本整数类型最大是 128 比特。不过即便是 128 比特的整数,最多也只能表示 39 个位数(38 个位数以下才是安全范围)而已,还算不上是本篇文章要介绍的「大数」。

事实上,很多编程语言的标准函数库已有内置超长整数的运算功能,我们只需要按照 API 文档来调用就好了。不过如果只关心加、减、乘、除运算的话,其实它们也没有到难以实作的地步,我们还是可以尝试自己动手写程序实作看看,来增进对数值计算的认识。

在开始想办法撰写程序前,先来简单了解一下数字系统(Numeral System)吧!

数字系统(Numeral System)

数字系统就是表示数字的方法。常用的表示方法有十进制、二进制、八进制和十六进制。

进制(进位)表示法

所谓进制(进位)表示法,就是在定义一个数在大于或等于某数的时候必须进位。好比我们最常用的十进制(十进位),当 #{{9 + 1}}# 要用数字表示为「十」的时候,因为 #{{9 + 1}}# 已经等于「十」,必须再往左进位,因此表示为 #{{10}}#。如果是八进制要表示「十」,可以看成 #{{7+1+2}}#,#{{7+1}}# 等于「八」,必须要进位,表示为 #{{10}}#,最后再加 #{{2}}# 的话就是 #{{12}}#。

以上的解释其实还是很模糊,来看看进制的两个通式吧!

通式一:一般式

#{{{
M_r = (a_n a_{n-1} \dots a_1 a_0 \text{ . } a_{-1} \dots a_{-(m - 1)} a_{-m})_r
}}}#

上面公式中,各代数的定义如下:

  • #{{M}}#:所要表示的数值。
  • #{{r}}#:底数(radix)。十进制以 10 为底;八进制以 8 为底,依此类推。
  • #{{n}}#:最高位的位数。(小数点前从 0 开始算)
  • #{{a}}#:每位数的数值。
  • #{{m}}#:小数点后最低位的位数。(小数点后从 1 开始算)
通式二:加权式

#{{{
M_r = a_n r^n + \dots + a_1 r^1 + a_0 r^0 + a_{-1} r^{-1} + \dots + a_{-m} r^{-m}
}}}#

上面公式中,各代数的定义同上面的通式一。

任何进制皆可借由加权式将值转换为十进制。例如有个八进制的数表示为 173(8),那么它的加权式就可以写成:

#{{{
173_{(8)} = 1 \times 8^2 + 7 \times 8^1 + 3 \times 8^0 = 123_{(10)}
}}}#

常用进制

十进制(Decimal)

十进制为我们最常用的进制系统,日常生活中所见的数字几乎都是以十进制来表示,例如金钱的数目、年龄、年份、数学。一般来说,未特别指定其进制的数值都会当作是十进制。十进制数值的表示方法如:789、789D、(789)10、789(10)。

二进制(Binary)

在数字的世界中常利用高电位(hi)和低电位(lo)来当作逻辑信号(没有电位称为高阻抗)。正逻辑 1 表示高电位,0 表示低电位;负逻辑 1 表示低电位,0 表示高电位。在一般情况下我们都是使用正逻辑。由于电子电路中的逻辑只有高电位 1 和低电位 0,故运算方式采用只有 1 与 0 的二进制系统。二进制数值的表示方法如:10110B、(10110)2、10110(2)、0b10110。

八进制(Octal)

为了方便让编程者控制内存的内容,可以将二进制数的 3 个连续的数字合并为 1 个(例如:10110(2)=26(8)),用 8 进制来表示,才不用输入一大串的 0 与 1。八进制数值的表示方法如:567O、(567)8、567(8)、0o567。

十六进制(Hexadecimal)

将二进制数的 4 个连续的数字合并为 1 个,即为十六进制。十六进制系统可以用在许多地方,除了前面说的可以简化二进制方便编程者控制内存的内容外,也可以用于色码(例如:#CFE0EA)。

十六进制的每个位数的最大值为「十五」,但一个阿拉伯数字并没有「十五」这种数值,故在 9 之后的数值会以英文字母来代替,例如「十」会写成 A、「十一」写成 B、「十二」写成 C、「十三」写成 D、「十四」写成 E、「十五」写成 F,依此类推。十六进制数值的表示方法如:3A2BH、(3A2B)16、3A2B(16)、0x3A2B。

例如要利用十六进制来指定某个 16 比特(2 个字节)的内存存入 1010101010101010B(1、0 交错)的数值,使用二进制来表示会显得很冗长,而且容易写错,这时可以改存入 AAAAH (1010(2)=A(16)),会清楚很多,且不易写错。

进制换算

为了能在撰写程序时在适当的时机运用各个进制来表示数值,学会进制的转换是必须的。

十进制转任何进制

十进制要转换成其他进制,整数部份可以利用连除法(可用短除法)来轻松达成,小数部份则需使用连乘法。

例题一:68.375 转 2 进制

首先将整数 68 做连除法(68 为被除数、2 为除数)运算,需将余数(remainder)写出来,除到被除数比除数小为止。

#{{{
\begin{alignedat}{2}
{68 \over 2} = 34 &{}\text{ ...}{}&& 0 \\
{34 \over 2} = 17 &{}\text{ ...}{}&& 0 \\
{17 \over 2} = 8 &{}\text{ ...}{}&& 1 \\
{8 \over 2} = 4 &{}\text{ ...}{}&& 0 \\
{4 \over 2} = 2 &{}\text{ ...}{}&& 0 \\
{2 \over 2} = 1 &{}\text{ ...}{}&& 0
\end{alignedat}
}}}#

此时只要将运算结果倒过来取最后的商(quotient)和所有余数值即可得到 68 的 2 进制值:

#{{{
68 = 1000100_{(2)}
}}}#

整数的部份转好后再来是小数的部份,将 0.375 的小数部份做连乘(乘以 2)计算,直到小数部份为 0。

#{{{
\begin{alignedat}{2}
0.375 \times 2 &{}= 0{}&&.75 \\
0.75 \times 2 &{}= 1{}&&.5 \\
0.5 \times 2 &{}= 1{}&&.0
\end{alignedat}
}}}#

此时只要将运算结果按照顺序取运算后的整数值即可得到 0.375 的 2 进制值:

#{{{
0.375 = 0.011_{(2)}
}}}#

合并上面的结果:

#{{{
68.375 = 1000100.011_{(2)}
}}}#

例题二:75.625 转 16 进制

首先将整数 75 做连除法(75 为被除数、16 为除数)运算,需将余数写出来,除到被除数比除数小为止。

#{{{
\begin{alignedat}{2}
{75 \over 16} = 4 &{}\text{ ...}{}&& 11
\end{alignedat}
}}}#

可知整数部份:#{{75 = 4B_{(16)}}}#。

整数的部份转好后再来是小数的部份,将 0.625 的小数部份做连乘(乘以 16)计算,直到小数部份为 0。

#{{{
\begin{alignedat}{2}
0.625 \times 16 &{}= 10{}&&
\end{alignedat}
}}}#

可知小数部份:#{{0.625 = A_{(16)}}}#。

合并上面的结果:

#{{{
75.625 = 4B.A_{(16)}
}}}#

任何进制转十进制

套用前面提到的加权式即可转换。

例题一:1000100.011(2) 转十进制

#{{{
\begin{alignedat}{2}
1000100.011_{(2)} &{}={}&& 1 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 \\
&{}\text{ }{}&& + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 \\
&{}\text{ }{}&& + 0 \times 2^0 + 0 \times 2^{-1} + 1 \times 2^{-2} \\
&{}\text{ }{}&& + 1 \times 2^{-3} \\
&{}={}&& 64 + 4 + 0.25 + 0.125 = 68.375
\end{alignedat}
}}}#

例题二:4B.A(16) 转十进制

#{{{
\begin{alignedat}{2}
4B.A_{(16)} &{}={}&& 4 \times 16^1 + 11 \times 16^0 + 10 \times 16^{-1} \\
&{}={}&& 64 + 11 + 0.625 = 75.625
\end{alignedat}
}}}#

进制的加减法

平常我们算数学都是使用十进制来计算,在加法若遇到大于或等于 10 的情况必须要进位;减法若遇到小于 0 的情况必须要借位。这个规则在其他进制也是一样,只不过加权值不同罢了。

加法

直接举个例子来讲解:

#{{{ 10111_{(2)} + 1001_{(2)} }}}#

从最小的位数(第 0 位)开始相加,#{{ 1 + 1 \geq 2}}#,因此进位,可以把式子写成:

#{{{ 10110_{(2)} + 1000_{(2)} + 10_{(2)} }}}#

往左一个位数(第 1 位),#{{1 + 0 + 1 \geq 2}}#,因此进位,可以把式子写成:

#{{{ 10100_{(2)} + 1000_{(2)} + 100_{(2)} }}}#

再左一个位数(第 2 位),#{{1 + 0 + 1 \geq 2}}#,因此进位,可以把式子写成:

#{{{ 10000_{(2)} + 1000_{(2)} + 1000_{(2)} }}}#

再左一个位数(第 3 位),#{{0 + 1 + 1 \geq 2}}#,因此进位,可以把式子写成:

#{{{ 10000_{(2)} + 10000_{(2)} }}}#

再左一个位数(第 4 位),#{{1 + 1 \geq 2}}#,因此进位,故最后算出来的结果为 #{{ 100000_{(2)} }}#。

减法

直接举个例子来讲解:

#{{{ 10111_{(2)} - 1001_{(2)} }}}#

从最小的位数(第 0 位)开始相减,#{{ 1 - 1 = 0 }}#,可以把式子写成:

#{{{ 10110_{(2)} - 1000_{(2)} }}}#

往左一个位数(第 1 位),#{{1 - 0 = 1}}#,式子不变。再往左一个位数(第 2 位),#{{1 - 0 = 1}}#,式子不变。

再往左一个位数(第 3 位),#{{0 - 1 < 0}}#,因此借位,可以把式子写成:

#{{{ 1110_{(2)} + 1000_{(2)} - 1000_{(2)} }}}#

故最后算出来的结果为 #{{ 1110_{(2)} }}#。

补数(complement)

任何 #{{r}}# 进制均有「#{{r-1}}# 的补数」与「#{{r}}# 的补数」。

例如一个二进制数,拥有 1 的补数(1's complement)和 2 的补数(2's complement);一个十进制数,拥有 9 的补数(9's complement)和 10 的补数(10's complement)。

#{{r - 1}}# 的补数

计算一个 #{{r}}# 进制数的 #{{r - 1}}# 的补数,只要将该数的每个位数分别当作减数,并以 #{{r - 1}}# 做为被减数来计算补数的每个位数。将 #{{r}}# 进制数与其 #{{r - 1}}# 的补数相加所得到的数,每个位数都会是 #{{r - 1}}#。

二进制的 1 的补数

计算一个二进制数的 1 的补数,只要将该数的「#{{0}}# 变 #{{1}}#、#{{1}}# 变 #{{0}}#」就好了。

例如 1100(2) 的 1 的补数为 0011(2)。

十进制的 9 的补数

计算一个十进制数的 9 的补数,只要分别用 #{{9}}# 减去该数的每个位数,把计算出来的每个差值(difference)作为补数的每个位数。

例如 123456789 的 9 的补数为 876543210。

#{{r}}# 的补数

把 #{{r}}# 进制数的 #{{r - 1}}# 的补数再加 #{{1}}#,就是 #{{r}}# 的补数。不过还有个比较快的计算方式,那就是从 #{{r}}# 进制数最小的位数开始(往左),「遇 #{{0}}# 写 #{{0}}#,用 #{{r - 1}}# 减去第一个非 #{{0}}# 的位数再加 #{{1}}#,然后用 #{{r - 1}}# 减去之后的每个位数」。

将 #{{r}}# 进制数与其 #{{r}}# 的补数相加所得到的数,每个位数都会是 #{{0}}#。

二进制的 2 的补数

计算一个二进制数的 2 的补数,只要先从最小比特(LSB, Least Significant Bit)开始(往左),「遇 #{{0}}# 写 #{{0}}#,遇第一个 #{{1}}# 写 #{{1}}#,之后的比特 #{{0}}# 变 #{{1}}#、#{{1}}# 变 #{{0}}#」。

例如 10110100(2) 的 2 的补数为 01001100(2)。

十进制的 10 的补数

计算一个十进制数的 10 的补数,只要先从个位数开始(往左),「遇 #{{0}}# 写 #{{0}}#,用 #{{9}}# 减去第一个非 #{{0}}# 的位数再加 #{{1}}#,然后用 #{{9}}# 减去之后的每个位数」。

例如 9876543210 的 10 的补数为 0123456790。

用 #{{r}}# 的补数表示负数

补数观念最常用于二进制系统,用以进行有号(signed)数的计算。以 3 比特整数为例,若我们把最大比特(MSB, Most Significant Bit)定义为整数的正负号,0 为正数;1 为负数,则这 3 比特整数可以表示的数值如下:

#{{{
\begin{alignedat}{2}
000_{(2)} &{}={}&& +0 \\
001_{(2)} &{}={}&& +1 \\
010_{(2)} &{}={}&& +2 \\
011_{(2)} &{}={}&& +3 \\
100_{(2)} &{}={}&& -0 \\
101_{(2)} &{}={}&& -1 \\
110_{(2)} &{}={}&& -2 \\
111_{(2)} &{}={}&& -3
\end{alignedat}
}}}#

不过这样的表示方式显然无法进行加减法计算。例如 #{{ 1 + (-1) = 001_{(2)} + 101_{(2)} = 110_{(2)} }}#,但 #{{ 110_{(2)} \neq 0 }}#。

所以我们要用补数来表示某最大比特为 0 的数的负数。利用 2 的补数,可以让 3 比特整数表示的数值如下:

#{{{
\begin{alignedat}{2}
000_{(2)} &{}={}&& +0 \\
001_{(2)} &{}={}&& +1 \\
010_{(2)} &{}={}&& +2 \\
011_{(2)} &{}={}&& +3 \\
100_{(2)} &{}={}&& -4 \\
101_{(2)} &{}={}&& -3 \\
110_{(2)} &{}={}&& -2 \\
111_{(2)} &{}={}&& -1
\end{alignedat}
}}}#

如此一来就可以正常地进行加减法计算了!例如:

#{{{ 1 + (-1) = 001_{(2)} + 111_{(2)} = 000_{(2)} = 0 }}}#

#{{{ 1 + (-3) = 001_{(2)} + 101_{(2)} = 110_{(2)} = -2 }}}#

#{{{ (-1) + (-3) = 111_{(2)} + 101_{(2)} = 100_{(2)} = -4 }}}#

十进制整数的大数运算

了解进制转换和补数的概念后,就可以先来实作看看十进制整数的大数运算的程序啦!

我们可以利用编程语言的基本整数类型组成数组,整个数组用来表示一个整数。数组的每个元素表示整数的每个「位数」,每个元素的最大值再加 1 表示这个整数的「底数」。数组最左端(索引 0 的位置)为最大位数,最右端为最小位数。

以十进制来举例,像是以下长度为 10 的数组:

索引    0   1   2   3   4   5   6   7   8   9
数值    1   2   3   4   5   6   7   8   9   0

这个数组所代表的整数即为 1234567890。

如果我们想要让数组能够表示更长的整数,除了可以增加数组的长度外,也可以增加数组的每个元素所能保存的数值长度。例如让数组的每个元素,最多都可以存十进制的两个位数的数值,那么这个数组就等同于是使用一百进制,如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   12  34  56  78  90   1   2   3   4   5

以上数组所代表的整数即为 12345678900102030405。

例如让数组的每个元素,最多都可以存十进制的三个位数的数值,那么这个数组就等同于是使用一千进制,如下:

索引    0   1   2   3   4   5   6   7   8   9
数值  123 456 789   1   2   3   4   5   6   7

以上数组所代表的整数即为 123456789001002003004005006007。

若我们的数组元素是 32 比特整数的话,最多可以安全地保存十进制的 9 个位数的数值,不过考虑到在乘法运算的时候,#{{a}}# 个位数的值乘上 #{{b}}# 个位数的值最多会有 #{{a + b}}# 个位数,为了避免溢出,每个元素最多就存十进制的 4 个位数的数值就好(也是可以存更多,只是乘法运算的时候要另外转型就是了),也就是要使用一万进位。然而,如果没有乘法运算,只有加、减和除法的话,可以让每个元素最多存十进制的 9 个位数的数值,这样性能会比较好。

为了让程序维护起来更方便,且更容易理解,我们将一个元素最多要保存多少个十进制的位数和数组的元素数量设成常数,并且如果方便的话,也定义出我们自己的 BigInteger 类型。代码如下:

如此一来,我们的大数运算程序能够支持的十进制的最大位数就会是 DIGIT_NUMBER_PER_ELEMENT * NUMBER_OF_ELEMENTS。如上面代码定义的值,就会是 400 位!

计算补数

补数的计算比较单纯,可以先实作这个功能。根据上面的数字系统介绍,为了要让我们的数组可以被用来表示负数,我们需要去计算这个数组的「#{{r}}# 的补数」,也就是从 #{{r}}# 进制数最小的位数开始(往左),「遇 #{{0}}# 写 #{{0}}#,用 #{{r - 1}}# 减去第一个非 #{{0}}# 的位数再加 1,然后用 #{{r - 1}}# 减去之后的每个位数」。至于这个「#{{r - 1}}#」就是 MAX_VALUE_PER_ELEMENT。

代码如下:

用字符串表示整数(将数组转成整数字串)

为了方便我们知道数组代表的整数数值到底是什么,我们可以撰写一个转换功能来将数组转成整数,不过由于转换出来的整数可能会很长,所以要用字符串来表示(整数字串)。

一开始我们要先判断这个数组到底是不是负数,只要判断数组的最大位数有没有超过 MAX_VALUE_PER_ELEMENT 的一半(可用 >> 1 来当作「除以 2」的运算)即可。如果超过了就是负数,要先取一次补数(也就是转正数)之后,让字符串以负号开头,再用补数继续转出整数字串。

至于转换的方式就是先从最大位数开始看,遇 0 就跳过,直到遇到非 0 的位数就填入字符串。接下来的位数不管是不是 0,都要填入字符串,在填入之前要先以 0 来补不足的十进制的位数,因为一个元素就是要有 DIGIT_NUMBER_PER_ELEMENT 个十进制的位数。如果都没遇到非 0 的位数,就回传字符串 0。

代码如下:

将整数字串转成整数

为了方便将整数甚至是很长的整数转成数组,我们可以撰写一个转换功能来将整数字串转成整数。

首先要先去判断字符串是否以负号 - 开头,如果是的话,就记录下来,并把 - 移除掉,当作正数来转换,最后再去计算结果的补数就是负数了。

至于转换的方式就是从字符串结尾开始,读取最多 DIGIT_NUMBER_PER_ELEMENT 个字符(长度最大为 DIGIT_NUMBER_PER_ELEMENT 的子字符串),将子字符串转成整数存进数组对应的索引位置中即可。

代码如下:

加法

计算两数组的相加结果很简单,根据前面介绍的补数加减法概念,我们完全不需要去管传进来的数组所代表的整数到底是正是负,直接进行加法就对了。

至于加法的方式,就是从最小位数开始,把两数组相同索引位置的元素相加,如果前次的加法运算有进位,还需要再将结果加 1,最后再重新记录有没有进位。

代码如下:

减法

计算两数组的相减结果很简单,根据前面介绍的补数加减法概念,我们完全不需要去管传进来的数组所代表的整数到底是正是负,直接进行减法就对了。

减法有两种实作方式,一种是将 a - b 的 b 取补数 b' 后,去计算 a + b'(利用前面实作的 add 方法),因为 b' = -b。不过这种方式的性能会比较不好一点。

采取另一种方式会比较好。就是从最小位数开始,把两数组相同索引位置的元素相减,如果前次的减法运算有借位,还需要再将结果减 1(减数加 1),最后再重新记录有没有借位。

代码如下:

乘法

计算 a、b 两数组的相乘的结果,即 a * b。要从最小位数开始把 b 的每个位数分别与 a 的所有位数相乘(一样从最小位数开始),并将结果加总。这边比较需要注意到的是,若以十位数乘上百位数,则结果会是从千位数起跳,换句话说,b 的第 dy 位数(0 是最大位数)乘上 a 的第 dx 位数,所得的结果要加到乘积(product)的第 NUMBER_OF_ELEMENTS - 1 - ((NUMBER_OF_ELEMENTS - 1 - dx) + (NUMBER_OF_ELEMENTS - 1 - dy)) 位,以 d 来表示这个式子算出来的值好了。如果这个 d 为负值,表示位数乘起来会超出数组所能代表的整数的最大位数,就不必再去计算位数相乘的结果了。

位数相乘后还要加上前次相乘的进位结果,再加上目前已计算的乘积的第 d 位,最后再重新记录进位的值。

在开始进行乘法计算前,要先判断两数组所代表的整数是否为负数,如果是的话就要先转补数,并且预测相乘结果会是正数还是负数,如果是负数的话,就必须还要再转一次补数。至于要怎么预测结果的正负,很简单,遵循「正负得负、负负得正」的规律就好了。

代码如下:

除法

除法的实作会比较困难一点,我们会需要先实作一个比较两个数组的大小的功能。比较大小时可以不必去管它们代表的整数是正的还是负的,都当成正的即可。

代码如下:

接下来就是除法的程序实作了。一开始和乘法一样要先把代表负整数的数组转补数,并预测结果是正的还是负的。

接着要持续把除数(b 数组)往左位移一个位数,找出最大但不超过被除数(a 数组)时的位移结果,以 t 来表示这个除数字移后的数组,并以 d 来表示往左位移的次数好了。

若被除数等于 t,除商(quotient)的第 NUMBER_OF_ELEMENTS - d - 1 位(0 为最大位数)即为 1,至此除商的结果就算完了。

若被除数大于 t,要让被除数持续与 t 相减,直到被除数小于 t,减的次数即为除商的第 NUMBER_OF_ELEMENTS - d - 1 位。若在减的过程中,被除数等于 t,则除商的第 NUMBER_OF_ELEMENTS - d - 1 位是减的次数再加 1,至此除商的结果就算完了。

就重复上述步骤,若剩余的被除数比除数小,除商的结果就算完了。

如果一开始预测的结果为负数的话,结果就必须要把除商的结果再转一次补数。

任意进制整数的大数运算

事实上我们已经实作出了「任意进制」整数的大数运算了。只要把上面实作的程序的 DIGIT_NUMBER_PER_ELEMENT 常数删掉,直接把数组元素的最大值填进 MAX_VALUE_PER_ELEMENT 常数中即可。例如要十六进制,就直接将 MAX_VALUE_PER_ELEMENT 常数设为 15。

当然,修改为不是以 10n 为基底的进制的话,就不能沿用先前实作的「字符串与整数互相转换」的功能了。这也就是为什么一开始要以计算「十进制整数」为目的来实作这个程序的原因,这样调试起来才方便嘛!