介紹
模數加法形成了一種數學結構，成為阿貝爾群（Abelian group）,這是以丹麥數學家阿貝爾的名字命名的，
前置知識
定義1. 設\(a,b\in Z\)，如果存在\(q\in Z\)使得\(a=qb\)，則稱\(b\)整除\(a\)，記為\(b|a\)，
定義2. 設\(a,b\in Z\)，\(b>0\)，\(a=qb+r\)，\(q\in Z\)，\(0\leq r<b\)，則稱\(r\)為\(a\)除以\(b\)所得到的余數，記為\(a\bmod b\)，
定義3. 設\(a,b,n\in Z\)，\(n>0\)，如果\(a\bmod n=b\bmod n\)，則稱\(a\)與\(b\)模\(n\)同余，記為\(a \equiv b\pmod{n}\)，
定理1. \(\forall a,b,n\in Z, n>0, a\equiv b\pmod{n}\)等價于\(n|(a-b)\)，
定理2.
- \(\forall a\in Z, a \equiv a \pmod{n}\)；
- \(\forall a, b\in Z\)，如果\(a\equiv b \pmod{n}\)，則\(b\equiv a\pmod{n}\)；
- \(\forall a,b,c\in Z\)，如果\(a\equiv b\pmod{n}\)并且\(b\equiv c\pmod{n}\)，則\(a\equiv c\pmod{n}\)；
- \(\forall a,b,k\in Z\)，如果\(a\equiv b\pmod{n}\)，則\(a+k\equiv b+k\pmod{n}\)；
- \(\forall a,b,c,d\in Z\)，如果\(a\equiv b\pmod{n}\)并且\(c\equiv d\pmod{n}\)，則\(a+c\equiv b+d \pmod{n}\)；
- \(\forall a,b,k\in Z\)，如果\(a\equiv b\pmod{n}\)，則\(ak\equiv bk\pmod{n}\)；
- \(\forall a,b,c,d\in Z\)，如果\(a\equiv b\pmod{n}\)并且\(c\equiv d\pmod{n}\)，則\(ac\equiv bd \pmod{n}\)；
- \(\forall a,b\in Z\)，\(ab \bmod n=(a\bmod n)(b\bmod n) \bmod n\)，
定義4. 設\(n\in Z\)，\(n>0\)，\(\forall x\in Z\)，定義\([x]=\{y|y\equiv 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. 設\(n\in Z\)，\(n>0\)，\(\forall x,y\in Z\)，\([x]=[y]\)當且僅當\(x\equiv y\pmod{n}\)，
模數加法構成阿貝爾群
- 設\(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,k\in 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 i\in Z\)，\([0]+[i]=[i]+[0]=[i]\)，這驗證了\([0]\)為單位元，
-
\(\forall i\in Z\)，\([n-i]+[i]=[i]+[n-i]=[n]=[0]\)，這說明\([i]\)有逆元，
以上驗證了\(Z_n\)對于加法運算“\(+\)”構成一個群，
- 設\(Z'_n=\{0,1,2,\cdots,n-1\}\)，在\(Z'_n\)上定義運算"\(\oplus\)"如下：\(i\oplus j=(i+j)\bmod n\)，則\((Z'_n,\oplus)\)構成一個群，
? 證明：
-
\(\forall a,b,c\in Z'_n,(a\oplus b)\oplus c=a\oplus (b\oplus 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\)
-
\(0\oplus a = (0+a)\bmod n = a\)
-
如果\(a\neq 0\)，則\((n-a)\oplus a = (n-a+a)\bmod n = 0\)；\(0\oplus 0=(0+0)\bmod n=0\)，
舉例
設用\(n\)個二進制位表示一個整數\(x\)，\(x\)的補碼定義為：
-
如果\(x\geq 0\)，則\(x\)的補碼為\(x\)的原碼；
-
如果\(x < 0\)， 則\(x\)的補碼為\(x+2^n\)的原碼，
例1：
設用8個二進制位表示一個整數，計算7和-7的補碼，
解：
-
因為\(7\geq 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種情況討論：
\(x\geq 0\)，\(y\geq 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+y\geq0\),計算結果的第\(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+y\geq0\),計算結果的第\(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）同余運算上，是互為逆元，
- 那么，\(a\oplus 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\) 的二進制表示（8位）\(0000\_0001\)，
- 然后取反加一，得\(1111\_1111\)，
- 現在令\(-1 = e + (- 1) = 0 + (- 1) = 0 - 1\)，
- 而變為二進制表示后\(0 - 1 = 0000\_0000 - 0000\_0001\)，
- 在第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 w\pmod{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
本文來自博客園，作者：江水為竭，轉載請注明原文鏈接：https://www.cnblogs.com/Az1r/p/16968337.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539632.html
標籤：其他
下一篇：有向圖的拓撲排序