从近世代数的角度理解补码

介绍

模数加法形成了一种数学结构，成为阿贝尔群（Abelian group）,这是以丹麦数学家阿贝尔的名字命名的。

前置知识

定义1. 设(a,bin Z)，如果存在(qin Z)使得(a=qb)，则称(b)整除(a)，记为(b|a)。

定义2. 设(a,bin Z)，(b>0)，(a=qb+r)，(qin Z)，(0leq r<b)，则称(r)为(a)除以(b)所得到的余数，记为(abmod b)。

定义3. 设(a,b,nin Z)，(n>0)，如果(abmod n=bbmod n)，则称(a)与(b)模(n)同余，记为(a equiv bpmod{n})。

定理1. (forall a,b,nin Z, n>0, aequiv bpmod{n})等价于(n|(a-b))。

定理2.

1. (forall ain Z, a equiv a pmod{n})；
2. (forall a, bin Z)，如果(aequiv b pmod{n})，则(bequiv apmod{n})；
3. (forall a,b,cin Z)，如果(aequiv bpmod{n})并且(bequiv cpmod{n})，则(aequiv cpmod{n})；
4. (forall a,b,kin Z)，如果(aequiv bpmod{n})，则(a+kequiv b+kpmod{n})；
5. (forall a,b,c,din Z)，如果(aequiv bpmod{n})并且(cequiv dpmod{n})，则(a+cequiv b+d pmod{n})；
6. (forall a,b,kin Z)，如果(aequiv bpmod{n})，则(akequiv bkpmod{n})；
7. (forall a,b,c,din Z)，如果(aequiv bpmod{n})并且(cequiv dpmod{n})，则(acequiv bd pmod{n})；
8. (forall a,bin Z)，(ab bmod n=(abmod n)(bbmod n) bmod n)。

定义4. 设(nin Z)，(n>0)，(forall xin Z)，定义([x]={y|yequiv x pmod{n}})，称为整数集(Z)上在模(n)同余的等价关系下的一个等价类。

例.

模(4)同余关系的所有等价类为：

• ([0]={cdots,-8,-4,0,4,8,cdots})
• ([1]={cdots,-7,-3,1,5,9,cdots})
• ([2]={cdots,-6,-2,2,6,10,cdots})
• ([3]={cdots,-5,-1,3,7,11,cdots})

定理3. 设(nin Z)，(n>0)，(forall x,yin Z)，([x]=[y])当且仅当(xequiv ypmod{n})。

模数加法构成阿贝尔群

1. 设(Z_n={[0],[1],cdots,[n-1]})为整数集(Z)上在模(n)同余的等价关系下所有等价类之集。

• 在(Z_n)上定义加法运算“(+)”如下：

• (forall [i],[j]in Z_n,[i]+[j]=[i+j])，则((Z_n,+))构成一个交换群；

• 在(Z_n)上定义乘法运算“(*)”如下：

• (forall [i],[j]in Z_n,[i]*[j]=[i*j])，则((Z_n,*))构成一个交换幺半群。

​ 证明：

• (forall i,j,i',j'in Z)，如果([i]=[i'])，([j]=[j'])，则([i+j]=[i'+j'])，这验证了“(+)”为一个运算。

• (forall i,j,kin Z)，(([i]+ [j])+ [k]=[i+j]+ [k]=[(i+j)+k])，([i]+ ([j]+ [k])=[i]+ [j+k]=[i+(j+k)])，(([i]+ [j])+ [k]=[i]+ ([j]+ [k]))，这验证了加法运算(+)满足结合律。

• (forall iin Z)，([0]+[i]=[i]+[0]=[i])，这验证了([0])为单位元。

• (forall iin Z)，([n-i]+[i]=[i]+[n-i]=[n]=[0])，这说明([i])有逆元。

  以上验证了(Z_n)对于加法运算“(+)”构成一个群。

2. 设(Z'_n={0,1,2,cdots,n-1})，在(Z'_n)上定义运算"(oplus)"如下：(ioplus j=(i+j)bmod n)，则((Z'_n,oplus))构成一个群。

​ 证明：

• (forall a,b,cin Z'_n,(aoplus b)oplus c=aoplus (boplus c))，结合律。

• (((a+b)bmod n+c)bmod n=(a+(b+c)bmod n)bmod n)

• (((a+b)bmod n+c)bmod n=(a+b+c)bmod n)

• ((a+(b+c)bmod n)bmod n=(a+b+c)bmod n)

• (0oplus a = (0+a)bmod n = a)

• 如果(aneq 0)，则((n-a)oplus a = (n-a+a)bmod n = 0)；(0oplus 0=(0+0)bmod n=0)。

举例

设用(n)个二进制位表示一个整数(x)，(x)的补码定义为：

• 如果(xgeq 0)，则(x)的补码为(x)的原码；

• 如果(x < 0)， 则(x)的补码为(x+2^n)的原码。

例1：

设用8个二进制位表示一个整数，计算7和-7的补码。

解：

• 因为(7geq 0)，因此7的补码为7的原码，即7的补码为0000_0111。

• 因为(-7 < 0)，因此-7的补码为(-7+2^8)的原码，即-7的补码为1111_1001。

(-7)的补码还可以这样求解：

• 先计算7的原码，得到0000_0111
• 然后取反加1，得到(-7)的补码为1111_1001。

例2：

设用8个二进制位表示一个整数，计算-128的补码。

解：

• 因为(-128 < 0)，因此-128的补码为(-128+2^8)的原码，即-128的补码为1000_0000。

• 同样的，(-128)的补码还可以这样求解：先计算128的原码，得到1000_0000，然后取反加1，得到(-128)的补码为1000_0000。

如果用(n)个二进制位表示一个整数，用补码表示的数字的范围为(-2^{n-1}sim 2^{n-1}-1)。

对于补码而言：

• 如果首位为0，其表示的是大于等于0的整数。
• 如果首位为1，其表示的是负数。

例3

如果用8个二进制位表示一个整数，00001010为哪个整数的补码？10001010为哪个整数的补码？

解：

• 因为00001010的首位为0，它为一个大于等于0的整数的补码，这个整数为(10)。
• 因为10001010的首位为1，它为一个负数的补码，这个负数为(138-2^8=-118)。

---

对补码加法的分类讨论

计算机中普遍采用补码表示数字的原因是对于负数的加法可以采用与自然数的加法一样的加法器 。

设(x)和(y)为任意的两个整数，分以下4种情况讨论：

(xgeq 0)，(ygeq 0)

• 此时(x)的补码为(x)的原码。
• (y)的补码为(y)的原码。
• 按照自然数相加计算得到(x+y)，恰为(x+y)的补码。

(x < 0)，(y geq 0)

• 此时(x)的补码为(x+2^n)的原码。
• (y)的补码为(y)的原码。
• 按照自然数相加计算得到(x+2^n+y=(x+y)+2^n)。
• 如果(x+y<0)，则得到的恰为(x+y)的补码；
• 如果(x+ygeq0),计算结果的第(n)位（从最右边数起，依次为第0位，第1位，(cdots)，第(n-1)位，第(n)位）会自动抛掉。这恰好就是在(bmod 2^n)。

(x geq 0)，(y < 0)

• 此时(x)的补码为(x)的原码。
• (y)的补码为(y+2^n)的原码。
• 按照自然数相加计算得到(x+(y+2^n)=(x+y)+2^n)。
• 如果(x+y<0)，则得到的恰为(x+y)的补码；
• 如果(x+ygeq0),计算结果的第(n)位会自动抛掉。

(x < 0)，(y < 0)

• 此时(x)的补码为(x+2^n)的原码。
• (y)的补码为(y+2^n)的原码。
• 按照自然数相加计算得到((x+2^n)+(y+2^n)=(x+y)+2^n + 2^n)，计算结果的第(n)位会自动抛掉，于是最终得到的计算结果为((x+y)+2^n)，恰为(x+y)的补码。

为什么是取反加一

相信大家一开始学习补码的时候都是记为取反加一，然而在看了本篇博客后，你或许明白了为什么是这样的。

设(x)为任意一个8位有符号整数（char），也就是说它的二进制位数为8位。

$x geq 0 $

• 此时(x)的补码为(x)的原码。

(x lt 0)

• 令(y = -x)，即(y)为(x)的相反数，y为正数。
• 令 (a)为(y)的二进制表示（原码），(b)为(x)的二进制表示（补码）。
• 那么由前面的知识，可以知道，(a)和(b) 在模(2^n)（n 为 二进制位数，这里为8）同余运算上，是互为逆元。
• 那么，(aoplus b=(a+b)bmod 2^n = (e) bmod 2^n = 0 = (2^n) bmod 2^n)。
• 所以，我们可以让(a + b = 2^n)。（让(a + b = 0)是一样的，原因在下）。
• 好，现在计算(b)。
• 对于一个n位二进制数，(2^n) 表示为(1_0000_0000) ，一共后面为(n)个0。（所以在计算机里，这个最高的1是不不存在的，是会被抛弃的，那么也可认为(a + b = 0)）
• 现在我们如何凑出这个数？显然，(a + a' = 1111_1111)。（(a'为对a按位取反， 结果一共n个1)）。
• 则，(a + a' + 0000_0001 = 1111_1111 + 0000_0001 = 1_0000_0000)。
• 这时候(b = a' + 0000_0001)， 即取反加一。

补码的连续性

现在我们研究下 -1。

1. 可以根据前面的知识，我们写出(1) 的二进制表示（8位）(0000_0001)。
2. 然后取反加一，得(1111_1111)。
3. 现在令(-1 = e + (- 1) = 0 + (- 1) = 0 - 1)。
4. 而变为二进制表示后(0 - 1 = 0000_0000 - 0000_0001)。
5. 在第9位上，可以借1，所以 (原式 = 1_0000_0000 - 0000_0001 = 1111_1111)。

补码这样的连续性使得我们在进行有符号数加减法时不需要考虑其他运算规则，直接相加即可。

---

负权

补码所表示的数，我们通常这样计算：

设表示的数为(w) ,二进制数表示为(s_ns_{n-1}s_{n-2}····s_{2}s_{1}，即)(s_i (1 le i le n))， (s_n)为符号位。

则

• 表示负数，(s_n = 1时)，(w = 2^{n - 1} * (-1) + sum_{i=0}^{n - 2} 2^{i})
• 表示非负数，(s_n = 0时)，(w = sum_{i=0}^{n - 2} 2^{i})

表示非负数很好理解，就是进制转换。

那么负数为什么要有负权呢？为什么最高位代表的权值是负的？

• 如果最高位我们视为正权，得到的值记为(w')，(w' = sum_{i=0}^{n - 1} 2^{i})。
• 显然，由之前的理论可以知道，(w' 与 (-w) 互为逆元)。即(w’ + (-w) = 2^n = 0 (bmod 2^n)) 。
• 但是(w + (-w) = 0 = 0(bmod 2^n))，相反数也是互为逆元。
• 那么它两就是等价类啊。但是它两的二进制表示是一样的，只是计算的方式不一样。
• 根据等价类的定理3， ([w']=[w])当且仅当(w'equiv wpmod{2^n})。
• 那么，因为(w' gt w)， 则(w' = w + 2^n)。则(w = w' - 2^n)。
• 而(2^n = 2^{n-1} + 2^{n-1})，也就说我们得减去两个最高位的1。
• 既然这样，令最高位的正权属性变为负权，不就正好是两个吗？
• 所以，定义最高位为1时，为负权 。

为什么是补码？

现在，让你设计一个正数负数都可以表示的运算系统，你会想到令一位为标志位 （Flag），来特殊地表示这个数是正数还是负数。

那么，计算机科学家们是先想到这样的编程思想（Flag位），还是先由近世代数进一步研究发现的呢？

我认为是由近世代数这样的思想进一步推广研究发现的。

毫无疑问，补码这些性质奠定了计算机科学的基础。

---

后记

这篇博客主要参考我的近世代数老师的讲义，他在上课时说，他当时在研究生推免答辩就问为什么计算机中要用补码，结果没有人答得上来。

参考资料：王义和.离散数学引论[M].哈尔滨：哈尔滨工业大学出版社，2007