同余定理与二进制补码

2022-10-14

我们知道，计算机使用2的补码（Two's complements）来表示负数。这样有一个好处：可以使用同一种运算规则来处理正负数的运算，否则，二进制的正数和负数相加，将会得到错误的结果。为了处理这个讹误，必须为负数设计一套“加法器”。关于这一部分的讨论，参照关于2的补码。

而补码使正负数使用同一套“加法器/乘法器”规则，实际上利用了同余运算的性质。

1. 同余定理 #

1.1 定义 #

同余定理是初等数论中讨论的内容，之所以在这里涉及，是为了解释计算机中采用补码来表示负数的设计原因。

同余定理的基本概念：给定一个正整数m（m>1），如果两个整数a和b满足a-b能被m整除，记作m|(a-b)，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。

亦即：对于 m>1，若有m|(a-b)，则a≡b(mod m)。

负数作为被除数，正数作为除数，它们的余数可以是正数也可以是负数。
比如 -8/3，其余数可以是1：(-3*3)+1，或者-2：(-2*3)-2。
这里就可以得出，-8≡-2≡1(mod 3)。
当然，这里还可以找出很多和-8同余的数。如-5，4，...

1.2 证明 #

充分性

若有m|(a-b)，证明a≡b(mod m):

因 m|(a-b)，
故有 a-b = pm；
设  a = p1*m + r1， b = p2*m + r2, 其中 0 < r1 < m，0 < r2 < m
故有 (p1-p2) * m + (r1 -r2) = pm
即 (r1 - r2) = p3 * m
又 0 < r1 < m， 0 < r2 < m
故r1 = r2
得证

必要性

若有 a % m = r， b % m = r，求证 (a-b) % m = 0

原式    = (q0*m + r - q1*m -r) % m 
        = (q0-q1)m % m
        = 0
得证

1.3 同于定理的基本性质 #

反身性：a≡a(mod m)
对称性：若a≡b(mod m)，则b≡a(mod m)
传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)
同余相加：若a≡b(mod m)，c≡d(mod m)，则a±c≡b±d(mod m)
同余相乘: 若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)
幂运算：若a≡b(mod m)，b≡c(mod m)，则aⁿ≡bⁿ(mod m)
除法：若ac≡bc(mod m) (c≠0)，则a≡b(mod m/gcd(c,m))，其中gcd(c,m)表示c和m的最大公约数

性质1、2、3显而易见。性质6可由性质5推导出，性质7不在此文中讨论。以下简单证明性质5，6：

求证 (a+c-b-d) % m = 0
原式 = (q1*m +q2*m) % m
     = (q1+q2)m % m
     = 0
得证

求证 (ac-bd) % m = 0
原式= (ac-bc+bc-bd) % m
    = [(a-b)c + (c-d)b] % m
    = (q1c + q2b)m % m
    = 0
得证

理解同余运算，及同余运算的基本性质，对于理解计算机使用反码来表示负数，以实现一种“加法器/乘法器”的内含。

2. 补码 #

计算机语言中，定义

正数的原码，反码，补码相等；
负数的原码，反码，补码各不相同；
- 原码：为其对应的正数的原码，不过最高位符号位由0变为1，表示负数；
- 反码：为其原码除符号位外按位取反的结果；
- 补码：为其反码 + 1的结果；

由上可知，负数在二进制中的表示为其正数“按位取反加1”的形式。

补码的本质是利用一个环，来实现同余运算，同余运算的性质告诉我们，它忽略符号。

以下的论述以8位机为前提。

在8位数情况下，可表示的数值范围是0~255共256个，在这个范围内取得的任意数，都是256的余数，你可以很清晰的看到:

若
a ≡ 1(mod 256)
b ≡ 2(mod 256)
则
r = a+b ≡ 3(mod 256)

如果想表示一个负数 -1，

x ≡ -1(mod 256)

即 256|(x+1)，在0~255范围呢，x只能是255。

即 255 ≡ -1(mod 256) ≡ 255(mod 256)

也就是说可以用255表示-1。

那么要表示一半正数，一半负数，恰好将二进制的最高位置为1就表示负数，置为0则表示正数，那么0~~255就可以表示〔-127~~127〕(-128?)的数值了。

那补码为什么是“取反+1”呢？

我们用~x表示x的按位取反值，那么可知 x + ~x = 255，则

x + ~x ≡255(mod 256) ≡ -1(mod 256)

即有

x + ~x + 1 ≡ 0(mod 256)

-x ≡ (~x + 1)(mod 256)

推导过程使用了同余定理的加法性质

以上。

可以看到，-x和~x+1模256同余，即我们可以用“取反加1”表示负数。

等等...

让我们讨论一下边际条件。

0~255一共256个数，-127~127一共255个数（不考虑-0的情况下），那么还多一个数128，128的二进制表示是10000000，最高位是1，按照高位1是负数，0是正数的原则，显然不能表示+128，那么它表示什么？

“-0的补码” #

-0的原码是10000000，我们通过“取反加1”的计算规则求得补码：

 原   1000 0000
 反   1111 1111
    +         1
---------------
 补 1 0000 0000

得到-0的补码是00000000，即还是0。

额外地，不妨使用上面的同余运算公式代入：

-0 ≡ (~0 + 1)(mod 256)
-0 ≡ (255 +1)(mod 256)
-0 ≡ 256(mod 256) ≡ 0(mod 256)

因此，0在二进制中没有正负之分。

虽然+0和-0的补码都是0，但是，0和-0的原码占用了00000000和10000000存储位置，似乎有“浪费资源”之嫌。完全可以让-0表示另一个数，实际上计算机也是这么做的。

由同余定理我们知道：

-128 ≡ 128(mod/256)

因此，计算机中使用10000000表示-128。

实际上我们可以通过计算规则证明这一点：

 补   1000 0000
    -         1
 ----------------
 反   0111 1111
 原   1000 0000

上述计算式证明了 [10000000]补 = [10000000]原，和同余定理的论证吻合。

因此，在8位机中，可表示的数值范围就是[-128，127]。

xf&pl