1. 机器计算的理论

机器为什么能够代替我们人脑进行算数运算？这其中要用到限位记数的理论。限位数理论主要解决如何用固定位数的数码来表示实数，进而实现用机器来进行数值运算。

1.1.  限位记数

所谓的限位记数就是记数的位数一定的记数方法，它来源于机器记数。在纸上用数码记数时不用考虑位数，如果使用算盘，记数的位数就被限制在一定的位数上。计算机也是一种机器，用计算机记数必然是限位记数。

1.1.1. 限位记数的基本概念

利用限位数可以表示正负数，变减法运算为加法运算。用计算机实现限位数的运算需要用到反码数和对称码数的概念。

数码和限位数

人类记数普遍采用数码由右向左排列的方式。所谓的数码，就是记数的基本单位，一般用阿拉伯数字或字符记号构成。例如，十进制的数码是0、1、2、3、4、5、6、7、8、9这十个字符，十六进制用的数码是0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F。

一种进制所用的数码是有限个，相邻数码的差是1，最小的数码用“0”表示，“1”是单位，这两个数码必不可少。将一个数码表示的十进制数叫数码的“值”，其中值最大的数码叫顶码，用@来记。

N是大于1的十进制整数，按着“逢N进一”的规则，用数码0、1、…、@由右向左记数，就可以写出N进制数。其中数码有N个，并且有N=@＋1。

定义1‑5  如果表数的位数固定，这些数就是限位数。

N进制的k位数最大的是@@@…@@，最小的数是000…00。限位数的无效数码不能省略，以表示位数。

为了方便，本书将n个数码重写用“^ⁿ”记在数码的右肩上。例如9^⁵表示99999。

反码

计算机设计中会用到反码，这里给出反码的定义。

定义1‑6  如果两个数码相加的结果是顶码，称一个是另一个的反码。

例如，十进制的数码（0，9）、（1，8）、（2，7）、（3，6）、（4，5）；八进制的（0，7）、（1，6）、（2，5）、（3，4）；二进制的（0，1）都是互为反码。

定义1‑7  如果将一个数的全部数码用每个数码对应的反码替换，得到的数就叫原数的反码数，也简称为反码。

显然，反码数也是相互的。

本书中，数a的反码记为!a。例如，!547 = 452。

限位数的数量

由于一种进制中数码的个数是一定的，如果记数的位数一定，那么数的总数就被确定了。例如3位的十进制数一共有1000个，也就是000～999这些数。这1000个数不论我们认为是整数还是小数，但数码排列的形式是不会变的，总的个数也不会变。例如，可以认为有小数点在三个数码间的某一位置，但不论小数点在那里，不会影响数的总数，书写的形式也不会改变，进位的关系也不变。

从数的多少来说，1000是三位数个数的上限，是三位数的总数，因此称它是三位十进制数的限数。很清楚，限数是不能用固定位数表示的最小正整数，它比限位表示的最大数多一个单位1。对于任意进制的限位记数给出如下定义。

定义1‑8  限位记数中数的总数叫限数。

显然记数的位数不同，那么限数也不会相同。例如在十进制中，2位数的限数是100，3位数的限数是1000，4位数的限数是10000，…

N进制中k位数的限数U=@^^k+1，限数是不能用k位数码写出的最小数。

1.  限位数运算的特点

限位数受到记数位数的限制，因而不论进行何种运算，只要结果超出了位数的限制，结果就不可能正确了。特别是作加法或乘法时，最左面的向上进位就得丢掉。

限位数运算的这种特点，从表面上看是一种不利的方面，然而恰是限位数运算的这种“不利”，使用机器表示正负数有了基本的方法。

用数码左右排列组成的限位数，从形式上看是没有小数点和符号位的，这与通常所说的非负整数相同，也就是无符号整数。如果不特别指出，本书就用限位数代替无符号整数。

2.  限位数的对称性

限位数有一个重要的特性，这个特性可以使我们能用较大的一部分限位数来表示负数，在机器记数中不用使用“＋－”符号或它们的其他代号。用限位数来表示正负数的方法，对计算机处理数运算设计十分有用。

如图1‑1所示，1～999是关于500成轴对称的，成轴对称的两数之和，正好是限数1000。

定义1‑9  和是限数的两个限位数的一个称为另一个的对称码。

例如，3位十进制数对（001，999）、（002，998）、…、（499，501）、（500，500）都是互为对称码的两个数组成的。

对称码的概念很容易得出一般的0和负数没有对称码的结论。由于000找不到一个三位数与之相加，结果为限数，故000没有对称码。

一个正数a的对称码用a’来记，“’”叫求补运算符。例如，452’是548，548’是452。

图1‑1  对称码的表数区间

从图1‑1可以看到，-500～500是关于原点0成轴对称的，因此可以建立-500～-1与500～999的一一对应关系，也就是说可以用500～999来表示-500～-1这些数。

3.  用限位数表示正负数

如果认为限位数500～999不是它们本身，而是-500～-1，就解决了用限位数表达正负数的问题。这样引进正负数之后，数的绝对值范围减少了一半，然而取得了机器表达正负数的关键性突破。从此在限位记数中，就可以不再使用“+”“-”号来标记一个数是正数还是负数了，在机器数值运算中也不必增加符号处理的麻烦。

由于500的对称码是自身，为了避免二义性，就规定对称点的数表示的是一个负数。那么表面上的500，实际上是-500。如此，三位十进制数采用这种不带正负号的正负数表达方式，表数的范围是-500～499的整数。

限位记数中，用较大的一部分数表示其对称码的相反数，在形式上没有了正负号，但最终还要表达成人们熟悉的有符号的十进制数。为此将限位数表达的十进制有符号数叫限位数的值，而将直接用数码书写出来无符号数，它的大小叫“表面值”。

值不论位数，可以不写无效“0”。值相等的两个限位数不论表示如何，都可以用等号“=”连接。例如，628的表面值就是628，而它的值是-372，可以记为628=-372。

4.  限位数的运算

限位数的运算是指表面值的运算，由于限位数运算的最高位进位会丢失，因而限位数运算的结果不一定与值的运算结果一致。例如，限位数的加运算是表面值的加运算，加运算的最高位进位会丢失，这正是它可能与值运算不一致的原因。

为了区分一般的数值运算和限位数的运算，特将限位数运算的表面值运算用“ó”连接。例如，512＋700ó212，结果是表面值运算的结果；而512的值是-488，700的值是-300，故512＋700 =(-488)+(-300)=-788。

看起来，限位数的表面值运算与值运算有很大的不同，但限位数的运算很多情况下与值运算是一致的。例如，312+876ó188，结果与值运算的结果一致，因为312的值就是本身，876的值是-124，值运算是312+(-124)=188。

在机器记数中，只要能够随时判断出限位数的表面值运算与值运算的不一致，并能够设法解决它，就可以完全用机器实现数值运算了。

1.1.2. 对称制

用无符号数来表示有符号的数，是限位记数的优点之一，特别是，这种表示可以变减法为加法运算，直接得到正确的结果，这在机器表数中十分有用。

例如945+876ó821，如果将这些数当作值看，这是一个错误的结果。如果将它们都看成是用不带符号数来表示的有符号数，那么945 = -055，876 = -124，821 = -179，那么实际值的结果完全是对的。

这种不带符号数的值的理解，很方便机器的运算设计，因而计算机中算术运算普遍使用这种无符号数表达形式。

定义1‑10   在限位记数中，规定负数用其相反数的对称码表示，其余不变，这就是对称制。

在对称制的表数中，表面上见不到负数，实际上可以非常方便地确定某一个数表示的是否是负数。判断的方法很简单，只要将表面值与全部数的对称点比较大小，立即就可以认定实际的值是多少。例如，三位十进制数只要看是否小于对称点500，是则为一个正数或0，否则就是一个负数。同样四位的十进制数的正负，要和对称点5000进行比较就可以知道值的正负。

对于限位十进制数，对称点的最高位是5，其余各位都是0，所以比较时只要比较最高位的数码就可以。最高位数码小于5的是0或正数，否则是负数。根据负数的对称码表示是该限位数对称码的相反数的约定，立即就可以求得它所表示的值。

例如，5675= -（10000-5675）= -4325。

1.1.3. 对称码和反码的关系

根据对称码和反码的定义，很容易利用一个数的反码来求这个数的对称码。例如，四位十进制数1234的反码是8765，而1234的对称码是10000 -1234=8766。由结果不难看到：一个数的对称码等于这个数的反码加1。

由前面的限位记数知道，互为反码的两个数的和的每一位都是顶码组成的数，而这个数的表面值是限位表示的最大数，与限数只差1，因而可以得到求一个限位数对称码的另一重要方法。

定理1‑1 一个限位数的对称码等于这个数的反码加1。

利用这一结论，求一个数的对称码不用作减法，可以直接通过反码加一进行，这对于机器运算来说十分方便。

1.1.4. 对称制加法的溢出

限位记数的表数范围是一定的，如果两个限位数作加法，结果的值超出范围，那么就不能用相同位数的限位数表达出来，这种情况叫溢出。

1.  加减法溢出的判断

两个限位数相加，为了能够得到正确的值，必须判断溢出。

溢出的判断非常简单，值符号相反的两个限位数相加，一定不会溢出，也就是说，溢出只发生在值符号相同的限位数相加的过程中。

定理1‑2  值同符号的两个限位数相加，结果改变符号才溢出，不然一定不溢出。

这个定理可以用绝对值的关系加以证明的，由于繁琐，在此不证。

值不同的两个限位数相减，可以转化成值相同的两个限位数相加，然后利用定理1‑2来判断是否溢出。例如，512-031=512+969 ó 481，由于512和969都是负数，相加的结果却得到了一个正数，依据定理1‑2，512-031结果溢出。

2.  溢出的解决方法

发生溢出的两个限位数加法，产生溢出的原因是由于最高位进位丢失造成的。如果扩大一位数，表数范围扩大了，那么再作这两个数的加法，结果就不会溢出了。

例如，780+590ó370，780和590的最高位数码都大于或等于5，表明它们的值都是负的，而370的值却是正数，可见这个表面值的加法运算发生了溢出，因而370不是要求的正确结果。

为了获得正确的结果，需要将固定的三位扩充到四位。扩充的关键是最高位添加什么数码。值为正数的限位数扩充，高位加无效0，这样不会改变原数的值。值为负数的限位数扩充就不能高位加0了，因为这样会改变了原数的值。

值为负数的限位数位数扩充，可以先将它的值的相反数扩充一位，然后变成对称制表示。例如，限位数769的值是-231，而 -231 = -0231，因此扩充成4位数的负数-231的对称制表示是9769，而3位数-231的对称码表示是769。由此可得限位数位数扩充的重要方法。

定理1‑3  值为负数的限位数位数扩充，要在填充位加顶码，不然在填充位添加“0”。

上面的780+590可以扩充成9780+9590ó9370= -630，这个结果是对的，因为780=-220，590= - 410，所以它们相加的值是-630。

1.1.5. 变减法为加法

限位记数不仅可以解决机器表数的正负问题，而更重要的是可以变减法运算为加法运算。例如，

123 - 456

=  123 + 544

ó 667

=  -333

这种变化是将最初值的减法运算转化成了对称制表示，由于减去一个数就是加上这个数的相反数，因而减法问题变成了加法。表面值相加的结果表示的是一个负数，它的值是正确的。

这种转换不论对减数是正数还是负数都可以。再如，

743 – 821

=743+179

ó922

= -78，

而743 = -257，821 = -179，-257-(-179) = -78，运算结果正确。

出于方便记录的需要，以下n个相同的数码x连写，记为下x^ⁿ。

限位记数变减法为加法的道理，可以如下认为：

设a、b是位数为n的限位数，那么限数是10ⁿ，但它的n位表示形式上就是n个0组成的数。由于

a-b = a+(0^ⁿ - b) ó a+(10ⁿ-b) = a+b’

这就告诉我们，形式上可以用限位记数的加法替代减法运算，当然结果有可能溢出，需要判断。如果加法运算产生溢出，可以用对称制位数扩充的方法，扩充一位得到正确的结果。

限位记数中减法可以用加法完成，这样加、减、乘、除，全部算术运算都可以用对称制加法运算来完成。