本文地址：https://www.cnblogs.com/faranten/p/16099916.html
轉載請注明作者與出處
1 資料和表示方法
1.1 數字的表示
1.1.1 定點數
? 在計算機中，數字分為定點數和浮點數兩類，“定點”的含義為小數點的位置是固定的，“浮點”則意味著小數點的位置不固定，簡單起見，定點數分為純小數和純整數，如果有一個數\(x\)在計算機中的存盤為\(x_nx_{n-1}\cdots x_1x_0\)，則
\[\begin{aligned} \text{純小數}&\quad x_n.x_{n-1}\cdots x_1x_0\qquad0\leq|x|\leq1-2^{-1}\\ \text{純整數}&\quad x_nx_{n-1}\cdots x_1x_0.\qquad0\leq|x|\leq2^n-1 \end{aligned}\quad(\text{其中}x_n\text{為符號位}) \]整型資料就是用定點數的方式表示的，
1.1.2 原碼、反碼、補碼、移碼
? 如果要讓資料具有正負性，有多種處理方式，一種最常見的方式就是原碼，它的思路就是單獨留出一個二進制位（位元）來表示符號，且該位不具備權重，即對于一個真值\(x\)而言，它在計算機中的原碼表示為\([x]_{\text{原}}\)：
\[[x]_{\text{原}}=x_nx_{n-1}\cdots x_1x_0,\quad x_n\text{是}x\text{的符號位},\quad x_{n-1}\cdots x_1x_0\text{是}|x|\text{的二進制表示} \]而反碼則是利用了實數軸的對稱性，真值\(x\)在計算機中的反碼表示為\([x]_{\text{反}}\)：
\[[x]_{\text{反}}= \begin{cases} x_nx_{n-1}\cdots x_1x_0,\quad x\geq0\\ \bar{x}_n\bar{x}_{n-1}\cdots\bar{x}_1\bar{x}_0,\quad x\leq0 \end{cases}\quad\text{其中}x_nx_{n-1}\cdots x_1x_0\text{是}|x|\text{的二進制表示} \]補碼則是將最高位視為一個特殊的帶權位，真值\(x\)在計算機中的補碼表示為\([x]_{\text{補}}\)：
\[[x]_{\text{補}}=\text{符號位}x_n\text{連接上} \begin{cases} x_{n-1}\cdots x_1x_0,\quad x\geq0\\ \bar{x}_{n-1}\cdots\bar{x}_1\bar{x}_0+1_{2},\quad x<0 \end{cases}\quad\text{其中}x_{n-1}\cdots x_1x_0\text{是}|x|\text{的二進制表示} \]其中\(\rightharpoondown\)表示對二進制中的每一位進行取反操作，上面的三個式子給出了從真值\(x\)生成機器表示的方法，下面給出從機器表示\(x_nx_{n-1}\cdots x_1x_0\)反解出真值的方法：
\[\begin{aligned} \text{原碼}&\quad x=(-1)^{x_n}\cdot\sum_{i=0}^{n-1}2^i\cdot x_i\\ \text{反碼}&\quad x=(-1)^{x_n}\cdot\sum_{i=0}^{n-1}2^i\cdot(x_i\oplus x_n)\\ \text{補碼}&\quad x=(-1)^{x_n}\cdot2^n+\sum_{i=0}^{n-1}2^i\cdot x_i \end{aligned} \]其中\(\oplus\)為異或運算，下面的表格給出了這三個表示方式的差別（以\(8\)個位元為例）：
| 計算機中存盤形式 | 原碼\(\rightarrow\)真值 | 反碼\(\rightarrow\)真值 | 補碼\(\rightarrow\)真值 |
|---|---|---|---|
| \(0000~0000\) | \(+0\) | \(+0\) | \(0\) |
| \(0000~0001\) | \(+1\) | \(+1\) | \(+1\) |
| \(0000~0010\) | \(+2\) | \(+2\) | \(+2\) |
| \(\dots\) | \(\dots\) | \(\dots\) | \(\dots\) |
| \(0111~1110\) | \(+126\) | \(+126\) | \(+126\) |
| \(0111~1111\) | \(+127\) | \(+127\) | \(+127\) |
| \(1000~0000\) | \(-0\) | \(-127\) | \(-128\) |
| \(1000~0001\) | \(-1\) | \(-126\) | \(-127\) |
| \(\dots\) | \(\dots\) | \(\dots\) | \(\dots\) |
| \(1111~1101\) | \(-125\) | \(-2\) | \(-3\) |
| \(1111~1110\) | \(-126\) | \(-1\) | \(-2\) |
| \(1111~1111\) | \(-127\) | \(-0\) | \(-1\) |
可以看出，不論是什么存盤方式，最高位始終可以起到標志正負的符號位作用，
? 至于移碼，這只是一個存盤上的技巧而已，主要用于比較大小，真值\(e\)在計算機中的移碼表示為\([e]_{\text{移}}\)：
\[[e]_{\text{移}}=e_ke_{k-1}\cdots e_1e_0,\quad e_ke_{k-1}\cdots e_1e_0\text{是}2^k+e\text{的二進制表示} \]其中\(e\)本身采用補碼表示，即\(-2^k\leq e\leq2^k-1\)，則\(0\leq e\leq2^{k+1}-1\)，相當于添加了一個偏置使其為正數，從硬體上來說，移碼更容易直接比較大小，
1.1.2 浮點數
? 定點數能夠表示的范圍是有限的，且定點數在它表示范圍內的不同區域中的精度是一樣的，考慮到任何數都能寫為
\[\begin{aligned} \text{十進制}&\quad N_{10}=M\times10^E\\ \text{二進制}&\quad N_{2}=M\times2^e \end{aligned} \]通過下面的定義
| 階符 | 階碼 | 數符 | 尾數 |
|---|---|---|---|
| \(E_s\) | \(E_{m-1}\cdots E_1E_0\) | \(M_s\) | \(M_{n-1}\cdots M_1M_0\) |
就能表示浮點數，其中階符和數符分別表示階碼和尾數的正負，并且可以發現，在不同區域，這樣定義的浮點數表示的數字的精度是不同的，精度取決于尾數的有效位數，在實際應用中，我們用 IEEE 754 標準定義浮點數，這包括單精度 float 浮點數和雙精度 double 浮點數：
| 31 | 30 - 23 | 22 - 0 |
|---|---|---|
| 符號位\(S\) | 階碼\(E=e+\text{Bias}_{32}\) | 尾數\(M\) |
| 63 | 62 - 52 | 51 - 0 |
|---|---|---|
| 符號位\(S\) | 階碼\(E=e+\text{Bias}_{64}\) | 尾數\(M\) |
? 下面先來看浮點數的生成方式，給定一個任意的無符號浮點數
\[x=x_nx_{n-1}\cdots x_1x_0.x_{-1}x_{-2}\cdots x_{-m+1}x_{-m} \]則通過移位，理想情況下我們能得到
\[x=x_i.x_{i-1}x_{i-2}\cdots x_{-m+1}x_{-m}\times2^{i-n},\quad\text{其中}x_i\text{為}x\text{二進制形式中最左側的}1 \]于是，理想情況下，我們將分別存盤\(x_i.x_{i-1}x_{i-2}\cdots x_{-m+1}x_{-m}\)和\(i-n\)兩個部分，不幸的是，這兩個之中總可能會有一個超出能夠表示的范圍：
- 如果\(x_i.\cdots\)的總位數是超出了分配給它的位數（而\(i-n\)的機器表示表示沒有超出分配給它的位數），考慮到此時總有\(x_i=1\)，故只需存盤\(.x_{i-1}\cdots\)，在單精度數中，這個純小數部分最多為\(23\)位，在雙精度中，這個純小數部分最多為\(52\)位，多余的位數被截斷
- 如果\(i-n\)的機器表示表示超出了分配給它的位數（單精度中為\(8\)位，雙精度中為\(11\)位）（而\(x_i.\cdots\)的總位數沒有超出分配給它的位數），有兩種具體的情況：
- 正數\(i-n\)過大，即小數點向左移動了太多還不能保證此小數點左側只有一個\(1\)，即\(x=x_jx_{j-1}\cdots.\cdots x_{-m}\times2^{e}\)（其中\(x_j=1\)），此時階碼取最大二進制表示（單精度中為\(8\)個\(1\)，雙精度中為\(11\)個\(1\)），這時候純小數部分\(.x_{j-1}\cdots\)最多為\(23\)位（單精度）或\(52\)位（雙精度）
- 負數\(i-n\)過小，即小數點向右移動了太多還不能保證小數點左側\(x_j=1\)，即此時\(x=x_j.x_{j-1}\cdots x_{-m}\times2^{e}\)（其中\(x_j=0\)），此時階碼取最小二進制表示（單精度中為\(8\)個\(0\)，雙精度中為\(11\)個\(0\)），這時候純小數部分\(.x_{j-1}\cdots\)最多為\(23\)位（單精度）或\(52\)位（雙精度）
- 如果兩部分都超過了各自的最大位數，這時優先保證量級正確，即先處理情況二（階碼超出），之后再處理情況一（小數部分超出）
如果階碼的機器表示沒有超出分配給它的位數，則這種數稱為規格化的數，它的特點是尾數\(M\)有隱含的\(1\)，偏置值為\(\text{Bais}_{32}=127\)或\(\text{Bais}_{64}=1023\)，階碼值為\(e=E-\text{Bais}\)，且階碼段既不是全\(1\)也不是\(0\)（因為全\(1\)和全\(0\)留給了后面的情況），如果階碼的機器表示超出了分配給它的位數，則這種數稱為非規格化數，它的特點是尾數\(M\)沒有隱含的\(1\)，階碼段為全\(1\)或全\(0\)，當階碼段為全\(0\)時，階碼值\(e=1-\text{Bais}\)（之所以不是\(0-\text{Bais}\)是為了保證非規格化數和規格化數的平滑過渡），當階碼段為全\(1\)時，它的含義后面敘述，
? 下面的表格以\(8\)位位元為例說明了 IEEE 754 浮點數定義的轉換方法和具體含義：
| 描述 | 位表示 | \(e\) | \(E\) | \(2^E\) | \(f\) | \(M\) | \(2^E\times M\) | \(V\) | 十進制 |
|---|---|---|---|---|---|---|---|---|---|
| \(0\) | \(0~0000~000\) | \(0\) | \(-6\) | \(\frac{1}{64}\) | \(\frac{0}{8}\) | \(\frac{0}{8}\) | \(\frac{0}{512}\) | \(0\) | \(0.0\) |
| 最小非規格化數 | \(0~0000~001\) | \(0\) | \(-6\) | \(\frac{1}{64}\) | \(\frac{1}{8}\) | \(\frac{1}{8}\) | \(\frac{1}{512}\) | \(\frac{1}{512}\) | \(0.001953\) |
| \(0~0000~010\) | \(0\) | \(-6\) | \(\frac{1}{64}\) | \(\frac{2}{8}\) | \(\frac{2}{8}\) | \(\frac{2}{512}\) | \(\frac{1}{256}\) | \(0.003906\) | |
| \(0~0000~011\) | \(0\) | \(-6\) | \(\frac{1}{64}\) | \(\frac{3}{8}\) | \(\frac{3}{8}\) | \(\frac{3}{512}\) | \(\frac{3}{512}\) | \(0.005859\) | |
| \(\cdots\) | |||||||||
| 最大非規格化數 | \(0~0000~111\) | \(0\) | \(-6\) | \(\frac{1}{64}\) | \(\frac{7}{8}\) | \(\frac{7}{8}\) | \(\frac{7}{512}\) | \(\frac{7}{512}\) | \(0.013672\) |
| 最小規格化數 | \(0~0001~000\) | \(1\) | \(-6\) | \(\frac{1}{64}\) | \(\frac{0}{8}\) | \(\frac{8}{8}\) | \(\frac{8}{512}\) | \(\frac{1}{64}\) | \(0.015625\) |
| \(0~0001~001\) | \(1\) | \(-6\) | \(\frac{1}{64}\) | \(\frac{1}{8}\) | \(\frac{9}{8}\) | \(\frac{9}{512}\) | \(\frac{9}{512}\) | \(0.017578\) | |
| \(\cdots\) | |||||||||
| \(0~0110~110\) | \(6\) | \(-1\) | \(\frac12\) | \(\frac{6}{8}\) | \(\frac{14}{8}\) | \(\frac{14}{16}\) | \(\frac78\) | \(0.875\) | |
| \(0~0110~111\) | \(6\) | \(-1\) | \(\frac12\) | \(\frac{7}{8}\) | \(\frac{15}{8}\) | \(\frac{15}{16}\) | \(\frac{15}{16}\) | \(0.9375\) | |
| \(0~0111~000\) | \(7\) | \(0\) | \(1\) | \(\frac{0}{8}\) | \(\frac{8}{8}\) | \(\frac{8}{8}\) | \(1\) | \(1.0\) | |
| \(0~0111~001\) | \(7\) | \(0\) | \(1\) | \(\frac{1}{8}\) | \(\frac{9}{8}\) | \(\frac{9}{8}\) | \(\frac{9}{8}\) | \(1.125\) | |
| \(0~0111~010\) | \(7\) | \(0\) | \(1\) | \(\frac{2}{8}\) | \(\frac{10}{8}\) | \(\frac{10}{8}\) | \(\frac54\) | \(1.25\) | |
| \(\cdots\) | |||||||||
| \(0~1110~110\) | \(14\) | \(7\) | \(128\) | \(\frac{6}{8}\) | \(\frac{14}{8}\) | \(\frac{1792}{8}\) | \(224\) | \(224.0\) | |
| 最大規格化數 | \(0~1110~111\) | \(14\) | \(7\) | \(128\) | \(\frac{7}{8}\) | \(\frac{15}{8}\) | \(\frac{1920}{8}\) | \(240\) | \(240.0\) |
| 正無窮大 | \(0~1111~000\) | - | - | - | - | - | - | \(+\infty\) | - |
| 負無窮大 | \(1~1111~000\) | - | - | - | - | - | - | \(-\infty\) | - |
| 非數 NaN | \(0/1~1110~\text{非}0\) | - | - | - | - | - | - | - | - |
可以看出，在不同區域，這樣定義的浮點數表示的數字的精度是不同的，
1.2 文字的表示
1.2.1 字符與字串
? 字符與字串采用 ASCII 碼進行存盤，它規定最高位為\(0\)，余下的\(7\)位可以給出\(128\)個編碼，包括大小寫英文字母、數字符、運算子和標點符號以及一些控制碼，常見的有：
- \(b_7b_6b_5b_4~b_3b_2b_2b_1=0011~0000=(48)_{10}=(30)_{16}\)開始的\(10\)個編碼表示數字符\(0\)到\(9\)
- \(b_7b_6b_5b_4~b_3b_2b_2b_1=0100~0001=(65)_{10}=(41)_{16}\)開始的\(26\)個編碼表示大寫字母
- \(b_7b_6b_5b_4~b_3b_2b_2b_1=0110~0001=(97)_{10}=(61)_{16}\)開始的\(26\)個編碼表示小寫字母
值得一提的是，此處的數字符與上面提到的資料的存盤不是一回事，上面的資料存盤的基于二進制存盤的（有權碼），而此處的數字符是直接基于十進制存盤的（無權碼），
? 有兩種存盤方式：大端法（big endian）和小端法（little endian），大端法的最高有效位元組在最前面，小端法的最低有效位元組在最前面，假設變數int a=0x01234567，則大端法（第一個表格）和小端法（第二個表格）形式分別為（按位元組編地址）：
0x100 |
0x101 |
0x102 |
0x103 |
||
|---|---|---|---|---|---|
| \(\cdots\) | 01 |
23 |
45 |
67 |
\(\cdots\) |
0x100 |
0x101 |
0x102 |
0x103 |
||
|---|---|---|---|---|---|
| \(\cdots\) | 67 |
45 |
23 |
01 |
\(\cdots\) |
一切跨越多個位元組的資料型別都需要考慮大小端法才能確定具體的存盤順序，其中每個位元組內部存盤的兩個數字順序是固定的，一個位元組的\(8\)個位元位被切分為兩個\(4\)位元位存盤資料，將\(0\)到\(9\)這\(10\)個數字編碼成\(4\)的方法有很多，比如 8421BCD 碼、格雷碼（及其他回圈碼）等等，
1.2.2 漢字
? 漢字在計算機中的存盤分為三種情況：
- 輸入時（漢字的輸入編碼）：
- 數字編碼：常用國標區位碼，用數字串代表一個漢字輸入，區位碼是將國家標準局公布的\(6793\)個漢字分為\(94\)個區，每個區分為\(94\)位，實際上把漢字表示成二維陣列，每個漢字在陣列中的下標就是區位碼，區碼和位碼各兩位十進制數字，因此輸入一個漢字需按鍵四次，例如“中”字位于第\(54\)區\(48\)位，區位碼為 \(5448\)
- 拼音碼：拼音碼是以漢語拼音為基礎的輸入方法，但漢字同音字太多，輸入重碼率很高，因此按拼音輸入后還必須進行同音字選擇
- 字形編碼：字形編碼是用漢字的形狀進行的編碼，全部漢字的部件和筆畫是有限的，把漢字的筆畫部件用字母或數字進行編碼，按筆畫的順序依次輸入，就能表示一個漢字，例如五筆字型編碼是最有影響的一種字形編碼方法
- 存盤時（漢字內碼）：漢字內碼是用于漢字資訊的存盤、交換、檢索等操作的機內代碼，一般采用\(2\)位元組表
示，英文字符的機內代碼是七位的 ASCII 碼，當用\(1\)位元組表示時，最高位為\(0\)，為了與英文字符能相互區別，漢字機內代碼中\(2\)位元組的最高位均規定為\(1\)，有些系統中位元組的最高位用于奇偶校驗位，這種情況下用\(3\)位元組表示漢字內碼 - 輸出時（漢字字模碼）：字模碼是用點陣表示的漢字字形代碼，它是漢字的輸出形式，簡易型漢字為\(16\times16\)點陣，提高型漢字為\(24\times24\)點陣、\(32\times32\)點陣甚至更高，因此字模點陣所占存盤空間很大，\(16\times16\)點陣的漢字要占用\(16\times16\div8=32\)位元組，國標兩級漢字要占用\(256\text{K}\)位元組，因此字模點陣只能用來構成漢字庫，而不能用于機記憶體儲，當顯示輸出或列印輸出時才檢索字庫，輸出字模點陣，得到字形，
2 定點運算
2.1 定點加減法（補碼）
? 對于定點數來說，加法和減法具有統一性，原因是因為
\[[x]_{\text{補}}+[y]_{\text{補}}=[x+y]_{\text{補}}\qquad[x]_{\text{補}}-[y]_{\text{補}}=[x-y]_{\text{補}} \]第一個式子可以分為四種情況來證明：
- \(x\geq0~\text{and}~y\geq0\)：相加為正數，因為正數的原碼補碼相同，則有\([x]_{\text{補}}+[y]_{\text{補}}=x+y=[x+y]_{\text{補}}\)
- \(x\geq0~\text{and}~y<0\)：相加可能為正可能為負，根據補碼的定義有\([x]_{\text{補}}+[y]_{\text{補}}=x+y+2^{n+1}=[x+y]_{\text{補}}\)
- \(x<0~\text{and}~y\geq0\)：和第二種情況一樣
- \(x<0~\text{and}~y<0\)：相加結果為負，根據補碼定義有\([x]_{\text{補}}+[y]_{\text{補}}=x+y+2^{n+1}+2^{n+1}=[x+y]_{\text{補}}\)
而第二個式子的證明如下：因為\([y]_{\text{補}}=[x+y]_{\text{補}}-[x]_{\text{補}}\)且\([-y]_{\text{補}}=[x+(-y)]_{\text{補}}-[x]_{\text{補}}=[x-y]_{\text{補}}-[x]_{\text{補}}\)，將此兩式相加得到
\[\begin{aligned} {[y]}_{\text{補}}+[-y]_{\text{補}} &=[x+y]_{\text{補}}-[x]_{\text{補}}+[x-y]_{\text{補}}-[x]_{\text{補}}\\ &=[x+y]_{\text{補}}+[x-y]_{\text{補}}-[x]_{\text{補}}-[x]_{\text{補}}\\ &=[(x+y)+(x-y)]_{\text{補}}-[x+x]_{\text{補}}\\ &=[x+x]_{\text{補}}-[x+x]_{\text{補}}=0 \end{aligned} \]因此\(-[y]_{\text{補}}=[-y]_\text{補}\)，所以\([x]_{\text{補}}-[y]_{\text{補}}=[x]_{\text{補}}+[-y]_{\text{補}}=[x-y]_{\text{補}}\)，
? 補碼的加法是在取模運算之下所做的運算，也就是說，超出應有位數的部分應當被舍棄，下面通過兩個例子來說明補碼加減法的具體操作：
例 已知\(x_1=+(14)_{10}=+(1110)_2\)，\(x_2=-(13)_{10}=-(1101)_2\)，求\(x_1+x_2\)
首先求出\([x_1]_{\text{補}}=0~1110\)以及\([x_2]_{\text{補}}=1~0011\)，相加得\(1~0~0001\)，丟棄第一位，得\(0~0001\)，即為\(+1\)，
例 已知\(x_1=+(13)_{10}=+(1101)_2\)，\(x_2=+(6)_{10}=+(0110)_2\)，求\(x_1-x_2\)
首先求出\([x_1]_{\text{補}}=0~1101\)以及\([-x_2]_{\text{補}}=1~1010\)，相加得\(1~0~0111\)，丟棄第一位，得\(0~0001\)，即為\(+7\)，
2.2 溢位的概念和檢測方法
? 當相加的兩數都比較大的時候，有可能出現加和之后的結果大于該范圍能表示的最大數的情況，該情況的直觀體現為
\[\text{正數}+\text{正數}\rightarrow\text{負數}\qquad\text{or}\qquad\text{負數}+\text{負數}\rightarrow\text{正數} \]需要注意的是，負數與正數相加（正數與負數相加）的不可能超出范圍的，下面先看兩個例子，再來分析溢位的原理和檢測方法：
例 已知\(x_1=+(11)_{10}=+(1011)_2\)，\(x_2=+(9)_{10}=+(1001)_2\)，求\(x_1+x_2\)
首先求出\([x_1]_{\text{補}}=0~1011\)以及\([x_2]_{\text{補}}=0~1001\)，相加得\(1~0100\)，即為\(-12\)，這顯然是荒唐的，
例 已知\(x_1=-(13)_{10}=-(1101)_2\)，\(x_2=-(11)_{10}=-(1011)_2\)，求\(x_1+x_2\)
首先求出\([x_1]_{\text{補}}=1~0011\)以及\([x_2]_{\text{補}}=1~0101\)，相加得\(1~0~1000\)，丟棄第一位，得\(0~1000\)，即為\(+8\)，這顯然是荒唐的，
? 溢位在區域上分為正溢（在正數范圍發生的溢位）和負溢（在負數范圍發生的溢位），在方向上分為上溢位（向大方向發生的溢位）和下溢位（向小方向發生的溢位），對于浮點數而言，一共有四種溢位情況：
| 不能表示 | 最大規格化數 | \(\cdots\) | 最小非規格化數 | 不能表示 | \(0\) | 不能表示 | 最小非規格化數 | \(\cdots\) | 最大規格化數 | 不能表示 |
|---|---|---|---|---|---|---|---|---|---|---|
| 負下溢 | 未溢位 | \(\cdots\) | 未溢位 | 負上溢 | \(0\) | 正下溢 | 未溢位 | \(\cdots\) | 未溢位 | 正上溢 |
而對于整型而言，正溢和上溢是相同的、負溢和下溢是相同的，
? 對整型而言，溢位的檢測辦法有兩個，其一是變形補碼法，例子為：
例 已知\(x_1=+(12)_{10}=+(1100)_2\)，\(x_2=+(8)_{10}=+(1000)_2\)，求\(x_1+x_2\)
首先求出\([x_1]_{\text{變補}}=00~1100\)以及\([x_2]_{\text{變補}}=00~1000\)，相加得\(01~0100\)，由于符號位為\(01\)，故發生了正溢位，
例 已知\(x_1=-(12)_{10}=-(1100)_2\)，\(x_2=-(8)_{10}=-(1000)_2\)，求\(x_1+x_2\)
首先求出\([x_1]_{\text{變補}}=11~0100\)以及\([x_2]_{\text{變補}}=11~1000\)，相加得\(1~10~1100\)，丟棄第一位，得\(10~1100\)，由于符號位為\(10\)，故發生了負溢位，
? 那么我們可以知道，變形補碼檢測溢位的法則為：
- 如果結果的兩位符號位相同，則未發生溢位
- 如果結果的兩位符號位不同，則\(01\)意味著正溢位，\(10\)意味著負溢位
該邏輯可用異或門實作，受此啟發，我們得到溢位的另一種檢測方法：單符號法
- 當最高有效位產生進位而符號位無進位時，產生正溢
- 當最高有效位無進位而符號位有進位時，產生負溢
下面用兩個例子說明這一點：
例 已知\(x_1=+(12)_{10}=+(1100)_2\)，\(x_2=+(8)_{10}=+(1000)_2\)，求\(x_1+x_2\)
首先求出\([x_1]_{\text{補}}=0~1100\)以及\([x_2]_{\text{補}}=0~1000\)，相加得\(1~0100\)，此時最高有效位產生了給符號位的進位\(1\)，而符號位沒有產生溢位的進位\(1\)，因此屬于正溢，
例 已知\(x_1=-(12)_{10}=-(1100)_2\)，\(x_2=-(8)_{10}=-(1000)_2\)，求\(x_1+x_2\)
首先求出\([x_1]_{\text{補}}=1~0100\)以及\([x_2]_{\text{補}}=1~1000\)，相加得\(1~0~1100\)，此時最高有效位沒有產生給符號位的進位\(1\)，而符號位卻產生了溢位的進位\(1\)，因此屬于負溢，
2.3 定點加減法（補碼）的門電路
? 定點加減法最簡單的實作是基于一位全加器的連接，下圖 (a) 為全加器的門電路（\(A_i\)和\(B_i\)為加數，\(C_i\)為來自上一位的進位），圖 (b) 為行波進位的加法減法器：
? 下面來分析延遲，在門電路分析中，我們選定信號通過與門或者或門的時間為\(T\)，且設經過異或門的時間為\(3T\)，則對于單個全加器而言，產生加和\(S_i\)的延遲為\(3T+3T=6T\)、產生進位\(C_{i+1}\)的延遲為\(3T+T+T=5T\)，對于較為復雜的門電路來說，要計算它的延遲就是要找到其中最長的時間鏈，對于上圖的行波進位的加法減法器來說，最長的時間鏈就是從\(A_0\)和\(B_0\)輸入經過\(n\)次進位最終產生溢位標志的鏈路，該鏈路所花費的時間為
\[3T(\text{對}B_0\text{預處理})+3T(A_0\text{和}B_0\text{的異或門})+n\cdot2T(n\text{次進位})+3T(\text{產生溢位符號的異或門})=(2n+9)T \]可以看出，這種方式的加法在進位上花費了大量的時間，下面來看先行加法的設計思路，該方法加速了加法程序，令\(P_i=A_i\oplus B_i\)、\(G_i=A_iB_i\)，則進位為\(C_{i+1}=G_i+P_iC_i\)，那么對于連續的加法而言：
\[\begin{aligned} C_1&=G_0+P_0C_0\\ C_2&=G_1+P_1C_1=G_1+P_1G_0+P_1P_0C_0\\ C_3&=G_2+P_2C_2=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0C_0\\ C_4&=G_3+P_3C_3=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_0\\ \cdots \end{aligned} \]這樣一直推下去，理論上說，任意位數的加法中的任意一個進位都可以根據直接輸入的數值計算出來（而不必依賴進位），根據多方面的考慮，常常以四位為一組，組內進行超前加法（先行加法、并行進位），而組之間使用傳統的進位加法（串行進位、即\(C_5\)依賴于進位而不是直接計算得到），每個這樣的單元稱為四位先行進位部件（Carry Look Ahead or CLA），每個這樣的單元延遲為\(2T\)（因為經過了一次多重與門和一次多重或門，且不考慮\(P_i\)和\(G_i\)的生成延遲），對于兩個\(16\)位數的不考慮溢位檢測的加法來說，使用四個這樣的單元就能完成加法程序，門電路如下圖所示：
左側的虛線框的功能是求出所有的\(P_i\)與\(G_i\)，中間虛線框的功能是進行串行進位操作，右側的虛線框的功能是根據\(A_i\)、\(B_i\)和\(C_i\)求出加和結果\(S_i\)，該結構中最長的時間鏈為從\(A_0\)和\(B_0\)進去、生成\(P_0\)、再經過先行進位與傳統進位到達最上面的 CLA、再經過求和操作得到最終的結果，延遲為
\[3T(\text{生成}P_0\text{的異或門})+2T(\text{產生}C_4\text{的時間})+2T(\text{產生}C_8\text{的時間})+2T(\text{產生}C_{12}\text{的時間})\\ +2T(\text{產生}C_{16}\text{的時間})+3T(\text{最后生成}S_{15}\text{的異或門的時間})=14T \]注意，最后生成\(S_{15}\)的時候只經過了一個異或門，因為\(S_{15}=A_{15}\oplus B_{15}\oplus C_{15}\)中的第一個異或門已經在更早的時候經過了，如果采用完全串行進位，則延遲為
\[3T(\text{對}B_0\text{預處理})+3T(A_0\text{和}B_0\text{的異或門})+(16-1)\cdot2T(15\text{次進位})=(2\cdot15n+9)T=39T \]可以看到延遲有較大的差異，這里加法不考慮溢位檢測，故不論是經由 CLA 實作的加法還是傳統的串行加法，都沒有考慮溢位檢測所花費的時間（因此傳統串行加法中的最后一次進位沒有必要），在 CLA 實作的加法中如果考慮溢位檢測，因為溢位檢測經過一個異或門（即\(C_{16}\oplus C_{15}\)）的延遲也為\(3T\)，因此總延遲不變，
2.4 定點乘法（原碼）
? 由于原碼與真值極為相似（只差一個符號），而乘積的符號又可以通過兩數符號的異或得到，因此，對于原碼的乘法而言，只需要忽略符號位進行典型的二進制乘法，最后在結果中單獨添加一個符號位即可，下面通過一個例子來說明：
例 已知\(x=-0.1110\)，\(y=-0.1101\)，求\([x\cdot y]_{\text{原}}\)
首先求出\([x]_{\text{原}}=1.1110\)以及\([y]_{\text{原}}=1.1101\)，然后取出不含符號位的\(1110\)和\(1101\)兩部分相乘，得到\(10110110\)，然后在前面加上符號位，得到\([x\cdot y]_{\text{原}}=0.10110110\)，
2.5 定點乘法（原碼）的門電路
? 下面討論不帶符號（即無符號數，原碼中不含符號位的部分的乘法也符合此情況）的陣列乘法器，不帶符號的陣列乘法器的門電路為：
被加數為一系列的\(a_ib_j\)，接下來的陣列乘法器將對這些被加數進行對應的加法，陣列乘法器為：
以上是五位二進制數乘以五位二進制數的陣列器，斜線表示來自上一級的進位輸入，最后輸出的結果為\(p_9p_8\cdots p_1p_0\)，對于這個器件來說，最長的鏈路為從\(a_4b_0\)與\(a_3b_1\)的全加器、到\(a_2b_2\)的全加器、到\(a_1b_3\)的全加器、到\(a_0b_4\)的全加器、到最后一行最右側的全加器、再經過\(3\)次進位到最后一行最左側的全加器、最后輸出\(p_8\)的鏈路，所以延遲為
\[T(\text{生成被加數的時間})+(n-2)\cdot6T(\text{豎直向下的傳遞時間})+5T(\text{沿斜線向最后一行的進位時間})\\ +(n-2)\cdot2T(\text{最后一行內部經過}n-2\text{次進位到達最左側全加器的時間})+3T(\text{生成}p_8\text{的一個異或門時間})\\ =(8n-7)T,\qquad33T(\text{上述}n=5\text{時}) \]? 如果我們輸入的是兩個原碼，那么根據上面的不帶符號的陣列乘法器，我們已經計算得到了不含符號位的乘法結果（比如輸入\(-3\)和\(5\)時，得到的是\(15\)），如果要使得到的結果也是補碼表示，那么在所得結果之前加上兩個乘數的符號位的異或即可，
2.6 定點乘法（補碼）
? 對于補碼形式的數而言，它的乘法規則不再顯然，通常我們先將這兩個數轉換為原碼形式（通過后面所述的求補器實作），再按照原碼的定點乘法規則（符號位單獨考慮）進行乘法，在得到的乘法結果前面加上單獨考慮的符號位，得到了原碼表示的結果，如果想讓最后的結果以補碼形式表示，則只需要在最后使其通過求補器即可，下面通過兩個例子說明該思路的具體操作程序：
例 已知\(x=+(13)_{10}=+(1101)_2\)，\(y=+(11)_{10}=+(1011)_2\)，求\(x\cdot y\)
首先求出\([x]_{\text{原}}=0~1101\)以及\([y]_{\text{原}}=0~1011\)，然后將不含符號的\(1101\)和\(1011\)相乘，得\(1000~1111\)，兩個符號位單獨異或，得到積的符號位為\(0\oplus0=0\)，則結果為\([x\cdot y]_{\text{原}}=0~1000~1111\)，即\(x\cdot y=+(1000~1111)=143\)，
例 已知\(x=+(3)_{10}=+0011\)，\(y=-(11)_{10}=-(1011)_2\)，求\(x\cdot y\)
首先求出\([x]_{\text{原}}=0~0011\)以及\([y]_{\text{原}}=1~1011\)，然后將不含符號的\(0011\)和\(1011\)相乘，得\(100001\)，兩個符號位單獨異或，得到積的符號位為\(0\oplus1=1\)，則結果為\([x\cdot y]_{\text{原}}=1~100001\)，即為\(x\cdot y=-(100001)=-33\)，
? 上面這種將補碼轉換為原碼的方法，在思路上很簡便，將補碼的情況轉變成了我們在2.4節中討論過的情況，下面介紹直接使用補碼進行乘法的思路，該思路不需要轉換為原碼，一定程度上減少了出錯的可能性，
? 補碼不能直接參與乘法的原因是：符號位的含義與后面的一般數碼沒有統一性，參考資料中唐朔飛著作中提到了當兩個乘數的補碼形式的符號任意時的Booth演算法，此處略去不談，
2.7 定點乘法（補碼）的門電路
? 之前現在我們已經討論了原碼的乘法器實作，如果試圖計算的是兩個補碼的乘法結果，那么對于輸入的補碼而言，根據2.6節的內容，先將這兩個數轉換為原碼形式（通過后面所述的求補器實作），再按照原碼的定點乘法規則（符號位單獨考慮）進行乘法，在得到的乘法結果前面加上單獨考慮的符號位，得到了原碼表示的結果，如果想讓最后的結果以補碼形式表示，則只需要在最后使其通過求補器即可，門電路如下所示：
其中求補器的門電路為：
當\(E=1\)時進行求補運算，當\(E=0\)時輸入和輸出一樣，該器件實作的思路為：從數的最右端\(a_0\)開始，由右向左，直到找出第一個\(1\)，例如\(a_i=1(0\leq i\leq n)\)，這樣，\(a_i\)以右的每一個輸入位，包括\(a_i\)自己，都保持不變，而\(a_i\)以左的每一個輸入位都求反，鑒于此，橫向鏈式線路中的第\(i\)掃描級的輸出\(C_i\)為\(1\)的條件是：第\(i\)級的輸入位\(a_i=1\)，或者第\(i\)級鏈式輸入（來自右起前\(i–1\)級的鏈式輸出）\(C_i–1=1\)，另外，最右端的起始鏈式輸入\(C_{–1}\)必須永遠置成\(0\)，如果我們有\(n+1=5\)位的輸入，由于符號位單獨考慮，則該求補器中最長的鏈路為：從\(C_{-1}\)開始、經過\((n+1)-1\)次進位、再經過一個與門和一個異或門輸出\(a_3^*\)的鏈路，因此延遲為
\[((n+1)-1)\cdot2T(n-1\text{次進位})+2T(與門)+3T(異或門)=(2n+5)T,\quad13T(\text{上述}n+1=5\text{時}) \]注意，和前面的假設不同的是，這里假設與門與或門延遲為\(2T\)，異或門延遲為\(3T\)，
? 最后指出，由于補碼的唯一性，我們既可以對補碼求補得到原碼（符號位單獨考慮），也可以對補碼求補得到原碼（符號位單獨考慮），
2.8 定點除法（原碼）
? 先來討論原碼的除法，由于在二進制除法中商數只可能是\(1\)，故余數減去一倍的除數只有兩種情況：夠減（減法結果大于零，此時令商為\(1\)）與不夠減（減法結果小于零，此時令商為\(0\)），在實際應用中，有兩種具體的思路：
- 恢復余數法：當不夠減的時候，恢復余數，并上商為\(0\)，進行后續的操作，這種思路最后得到的余數是準確的
- 加減交替法：夠減則下一步進行減法、不夠減則下一步進行加法，這種思路最后得到的余數可能需要糾正
為了避免不夠減時回傳去重新計算，我們采用加減交替的思路，它的原理由下式保證
\[\begin{aligned} \text{若}r_i'=2r_{i-1}-y>0&\quad\text{則}r_i=r_i'\text{且}r_{i+1}'=2r_i-y=2r_i'-y\\ \text{若}r_i'=2r_{i-1}-y<0&\quad\text{則}r_i=r_i'+y\text{且}r_{i+1}'=2r_i-y=2r_i'+y \end{aligned} \]其中\(r_{i-1}\)是當前的余數（即將作為被減數，減數為除數\(y\)），\(r_i'=2r_{i-1}-y\)可能是新的余數（如果該數大于零則是，小于零則不是）（大于零則令商為\(1\)，小于零則令商為\(0\)），\(r_i\)是真的新的余數（但我們只關心最后的結果商，而不關心這種中途生成的余數），從上式可以看出，下一級的可能余數\(r_{i+1}'\)的生成方式取決于當前的可能余數\(r_i'\)（減去除數\(y\)或加上除數\(y\)），如果\(r_{i+1}'>0\)則下一位商置為\(1\)，如果\(r_{i+1}'<0\)則下一位商置為\(0\)，如此不斷進行下去，直到出現某個\(r_j=0\)或者到達最大精度，
? 上面討論的原碼除法，適用于任何原碼之間的除法（正數與正數、正數與負數、負數與正數、負數與負數，中間兩種的符號位單獨處理），雖然稱為原碼乘法，但運算中涉及到的加減法仍然是補碼的，所謂“原碼”僅是指參與除法的兩個數需要先取絕對值才能才與運算，至于商數的符號位則單獨確定，這和原碼乘法是類似的，但不同之處在于，原碼乘法中不涉及到減法而原碼除法涉及到減法，
? 我們在此只討論了原碼（即無符號數，原碼中不含符號位的部分的乘法也符合此情況）的除法原理，有符號數（比如補碼）的情況后面再談，后面的例子說明這一點，下面通過兩個例子說明原碼定點除法的實作程序：
例 已知\(x=+(9)_{10}=+(1001)_2\)，\(y=+(11)_{10}=+(1011)_2\)，求\(x\div y\)
首先求出\([x]_{\text{原}}=0~1001\)以及\([y]_{\text{原}}=0~1011\)，然后取絕對值（即所謂的無符號數）\(0~1001\)和\(0~1011\)依次進行下面的操作：
| \(i\) | 被除數 | 除數 | \(2r_{i-1}'\) | \(r_i'=2r_{i-1}'\pm y\) | 商 |
|---|---|---|---|---|---|
| \(1\) | \(0~1001\) | \(0~1011\) | 被除數 | \(\text{被除數}-0~1011=0~1001+1~0101=1~1110<0\) | \(0\) |
| \(2\) | \(0~1001\) | \(0~1011\) | \(1~1100\) | \(1~1100+0~1011=1~0~0111\)，丟棄第一位得\(0~0111>0\) | \(1\) |
| \(3\) | \(0~1001\) | \(0~1011\) | \(0~1110\) | \(0~1110-0~1011=1~0~0011\)，丟棄第一位得\(0~0011>0\) | \(1\) |
| \(4\) | \(0~1001\) | \(0~1011\) | \(0~0110\) | \(0~0110-0~1011=1~1011<0\) | \(0\) |
| \(5\) | \(0~1001\) | \(0~1011\) | \(1~0110\) | \(1~0110+0~1011=1~0~0001\)，丟棄第一位得\(0~0001>0\) | \(1\) |
| \(\cdots\) | \(0~1001\) | \(0~1011\) | \(\cdots\) | \(\cdots\) | \(\cdots\) |
然后對符號位單獨異或\(0\oplus0=0\)，因此\([\text{商}]_{\text{原}}=0.1101\)（第一位是符號位），
例 已知\(x=+(9)_{10}=+(1001)_2\)，\(y=-(11)_{10}=-(1011)_2\)，求\(x\div y\)
首先求出\([x]_{\text{原}}=0~1001\)以及\([y]_{\text{原}}=1~1011\)，然后取絕對值（即所謂的無符號數）\(a=0~1001\)和\(b=0~1011\)依次進行下面的操作：
| \(i\) | 被除數\(a\) | 除數\(b\) | \(2r_{i-1}'\) | \(r_i'=2r_{i-1}'\pm y\) | 商 |
|---|---|---|---|---|---|
| \(1\) | \(0~1001\) | \(0~1011\) | 被除數 | \(\text{被除數}-0~1011=0~1001+1~0101=1~1110<0\) | \(0\) |
| \(2\) | \(0~1001\) | \(0~1011\) | \(1~1100\) | \(1~1100+0~1011=1~0~0111\)，丟棄第一位得\(0~0111>0\) | \(1\) |
| \(3\) | \(0~1001\) | \(0~1011\) | \(0~1110\) | \(0~1110-0~1011=1~0~0011\)，丟棄第一位得\(0~0011>0\) | \(1\) |
| \(4\) | \(0~1001\) | \(0~1011\) | \(0~0110\) | \(0~0110-0~1011=1~1011<0\) | \(0\) |
| \(5\) | \(0~1001\) | \(0~1011\) | \(1~0110\) | \(1~0110+0~1011=1~0~0001\)，丟棄第一位得\(0~0001>0\) | \(1\) |
| \(\cdots\) | \(0~1001\) | \(0~1011\) | \(\cdots\) | \(\cdots\) | \(\cdots\) |
然后對符號位單獨異或\(0\oplus1=1\)，因此\([\text{商}]_{\text{原}}=1.1101\)（第一位是符號位），
? 下面來看糾正余數的問題，采用加減交替法的原碼除法的一個小缺陷就是最后得到的余數可能不是真正的余數（但最后得到的商數一定是真的商數），原碼除法的余數糾正并不是明晰的，因為它涉及到原碼和補碼的轉換，我們將在后面補碼除法除法中詳細說明余數糾正的一般規則，
2.9 定點除法（原碼）的門電路
? 從上面的內容，我們不難發現，原碼的定點除法具有下面的特征：
- 在形式上永遠是正數和正數的除法（因為取了絕對值）
- 被除數不需要在計算程序中保存，除數需要在計算程序中保存并向下一級傳遞
- 每次計算的可能余數\(r_i'\)在參與下一級運算之前需要左移一位（該操作模擬的是真實除法程序中在余數后面加上一個\(0\)的程序）
- 由于通過加減交替的思路實作，故內部應該整合一個進行補碼加減法的門電路
根據上面的特征，我們可以設計出可控加法減法（CAS）單元如下：
在計算的一開始，\(A_i\)為被除數的某一位，在后面的程序中，\(A_i\)為\(2r_i'\)的某一位，\(P=0\)則進行加法運算，\(P=1\)則進行減法運算，\(B_i\)為除數的某一位（將保持不變向下傳遞），\(C_i\)為來自上一級的進位（進行加法時\(C_{-1}=0\)，進行減法時\(C_{-1}=1\)），\(S_i\)為加和結果，\(C_{i+1}\)為進位結果，下圖展示了如何將這些單元組合起來構成\(4\)位除\(4\)位的陣列除法器：
（最后得到的是不含符號位的商），其中，沿著斜線輸入的\(0y_3y_2y_1\)為除數，沿著豎線輸入的\(0x_6x_5x_4x_3x_2x_1\)為被除數，對于第一行而言，第一次執行的操作為減法，故輸入\(P=1\)（且第一行最右側輸入的\(C_{-1}=P=1\)），第一行最左側的進位輸出用于判斷可能余數的正負（由此決定下一次進行加法還是減法），如果進位為\(0\)則說明可能余數為負數（此時令商為\(0\)且下一次進行加法），如果進位為\(1\)則說明可能余數為正數（此時令商為\(1\)且下一次進行減法），從例\(11\)也可以看出，正數總是通過丟棄最高位才得到的，這實際上由更深入的原理來保證，在嚴格的\(4\)位除\(4\)位的除法當中，被除數\(0x_6x_5x_4x_3x_2x_1=0x_6x_5x_4000\)，在除法向下推進的程序中，上一次得到的可能余數的最高位不再參與運算，并在最低位引入\(x_3\)或\(x_2\)或\(x_1\)，這滿足了可能余數\(r_i'\)在參與下一級運算之前需要左移一位的要求，
? 現在來分析延遲，在上述所示的\(4\)位除\(4\)位的陣列除法器中，我們記真正有效的位數\(3\)為\(n\)，則被除數有效部分為\(2n\)，除數有效部分為\(n\)，陣列除法器一共有\((n+1)^2\)個 CAS 單元，該陣列除法器中最長的鏈路為：從\(P=1\)輸入開始，經過每一行的每一次進位再進入下一行、直到最后生成最后一個商\(p_1\)的時間，因此延遲為
\[(n+1)^2\cdot3T((n+1)^2\text{次進位時間})=3(n+1)^2T,\quad48T(\text{上述}n=3\text{時}) \]2.10 定點除法（補碼）
? 現在略去具體的推導（詳見參考資料中唐朔飛著作），直接給出補碼除法的一般規則：
| \([x]_{\text{補}}\)與\([y]_{\text{補}}\) | 商 | \([R]_{\text{補}}\)與\([y]_{\text{補}}\) | 上商 | 下一步 |
|---|---|---|---|---|
| 同號 | 正數 | 同號，表示夠減 | \(1\) | \(+[-y]_{\text{補}}\) |
| 同號 | 正數 | 異號，表示不夠減 | \(0\) | \(+[y]_{\text{補}}\) |
| 異號 | 負數 | 異號，表示夠減 | \(0\) | \(+[y]_{\text{補}}\) |
| 異號 | 負數 | 同號，表示不夠減 | \(1\) | \(+[-y]_{\text{補}}\) |
下面通過兩個例子加以說明：
例 已知\(x=-1001\)，\(y=+1101\)，求\(x\div y\)
首先求出\([x]_{\text{補}}=1~0111\)以及\([y]_{\text{補}}=0~1101\)，計算程序如下：
| \(i\) | \([x]_{\text{補}}\) | \([y]_{\text{補}}\) | \(2r_{i-1}'\) | \(r_i'=2r_{i-1}'\pm y\) | 商 |
|---|---|---|---|---|---|
| \(1\) | \(1~0111\) | \(0~1101\) | 被除數 | \(1~0111+0~1101=1~0~0100\)，丟棄第一位得\(0~0100\)與\([y]_{\text{補}}\)同號 | \(1\) |
| \(2\) | \(1~0111\) | \(0~1101\) | \(0~1000\) | \(0~1000-0~1101=1~1011\)，與\([y]_{\text{補}}\)異號 | \(0\) |
| \(3\) | \(1~0111\) | \(0~1101\) | \(1~0110\) | \(1~0110+0~1101=1~0~0011\)，丟棄第一位得\(0~0011\)與\([y]_{\text{補}}\)同號 | \(1\) |
| \(4\) | \(1~0111\) | \(0~1101\) | \(0~0110\) | \(0~0110-0~1101=1~1001\)，與\([y]_{\text{補}}\)異號 | \(0\) |
| \(\cdots\) | \(1~0111\) | \(0~1101\) | \(\cdots\) | \(\cdots\) | \(\cdots\) |
因此\([x\div y]_{\text{補}}=1.010\)，故\(x\div y=-0.110\)，
例 已知\(x=+1001\)，\(y=+1101\)，求\(x\div y\)
首先求出\([x]_{\text{補}}=0~1001\)以及\([y]_{\text{補}}=0~1101\)，計算程序如下：
| \(i\) | \([x]_{\text{補}}\) | \([y]_{\text{補}}\) | \(2r_{i-1}'\) | \(r_i'=2r_{i-1}'\pm y\) | 商 |
|---|---|---|---|---|---|
| \(1\) | \(0~1001\) | \(0~1101\) | 被除數 | \(0~1001-0~1101=1~1100\)，與\([y]_{\text{補}}\)異號 | \(0\) |
| \(2\) | \(0~1001\) | \(0~1101\) | \(1~1000\) | \(1~1000+0~1101=1~0~0101\)，丟棄第一位得\(0~0101\)與\([y]_{\text{補}}\)同號 | \(1\) |
| \(3\) | \(0~1001\) | \(0~1101\) | \(0~1010\) | \(0~1010-0~1101=1~1101\)，與\([y]_{\text{補}}\)異號 | \(0\) |
| \(4\) | \(0~1001\) | \(0~1101\) | \(1~1010\) | \(1~1010+0~1101=1~0~0111\)，丟棄第一位得\(0~0111\)與\([y]_{\text{補}}\)同號 | \(1\) |
| \(\cdots\) | \(0~1001\) | \(0~1101\) | \(\cdots\) | \(\cdots\) | \(\cdots\) |
因此\([x\div y]_{\text{補}}=0.101\)，故\(x\div y=+0.101\)，
? 下面來看余數的糾正：
- 如果當前上商為\(1\)，則當前余數就是真余數
- 如果當前上商為\(0\)，則當前余數需要加上\([y]_{\text{補}}\)才是真余數
來看例子：
- 上面第一個例，\(i=4\)時，上商\(0\)，真余數為\(0~0110\)
- 上面第一個例，\(i=3\)時，上商\(1\)，真余數為\(0~0011\)
- 上面第二個例，\(i=4\)時，上商\(1\)，真余數為\(1~1010\)
- 上面第二個例，\(i=3\)時，上商\(0\)，真余數為\(0~1010\)
2.11 定點除法（補碼）的門電路
? 結構和原碼的除法門電路一樣，只不過涵蓋了符號位，且檢測上商的時候不僅需要可能余數\([R]_{\text{補}}\)的符號位、而且需要除數\([y]_{\text{補}}\)，這兩者同號則上商\(1\)，否則上商\(0\)，另外，原碼除法必定是正數除以正數，所以第一步一定進行的是減法，但在補碼除法中如果被除數和除數同號則第一步進行減法、否則進行加法，所以首先輸入的\(P\)可能是\(1\)（進行減法）、也可能是\(0\)（進行加法），
5 浮點運算
5.1 浮點加減法
? 完成浮點加減法的大致程序分為四步：
- \(0\)運算元檢查
- 比較階碼大小并完成對階
- 尾數進行加減運算
- 結果規格化并進行舍入處理
接下來結合下圖說明具體程序：
上圖顯示的是\(x\pm y\)的操作程序，在對階操作中，總是小階向大階對齊，比如\(x=1.000_2\times2^{-1}\)，\(y=-1.110_2\times2^{-2}\)，則\(y\)應該轉成\(y=-0.111_2\times2^{-1}\)，注意，在此對階程序中可能出現尾數丟失的問題，因此要進行所謂的舍入處理（后面敘述），在對階完成之后，進行加減法，然后對尾數進行規格化處理，此時在規格化時也涉及到了舍入處理，現在來討論這個處理的具體內容，舍入處理發生在對階和向右規格化時，這樣，被右移的尾數的低位部分就會被丟掉，從而造成一定誤差，所以進行舍入處理，常見的舍入處理有下面幾種：
- 就近舍入：就是”四舍五入“，例如，若被舍棄的五位二進制位為\(10010\)，則丟棄這五位之后的最低二進制位因該加一；若被舍棄的四位二進制位為\(0111\)，則丟棄這四位之后的最低二進制位保持不變
- 朝\(0\)舍入：即朝數軸原點方向舍入，就是簡單的截尾，無論尾數是正數還是負數，截尾都使取值的絕對值比原值的絕對值小，這種方法容易導致誤差累積
- 朝\(+\infty\)舍入：對正數來說，只要多余位不全為\(0\)則向最低有效位進\(1\)；對負數來說，則是簡單的截尾
- 朝\(-\infty\)舍入：對負數來說，只要多余位不全為\(0\)則向最低有效位進\(1\)；對正數來說，則是簡單的截尾
同時，在最后對結果進行規格化的程序中，階碼可能會溢位，常見的階碼溢位和處理手段如下所示：
- 階碼上溢：超過了階碼可能表示的最大值的正整數值，一般將其認為是\(+\infty\)和\(-\infty\)
- 階碼下溢：超過了階碼可能表示的最小值的負指數值，一般將其認為是\(0\)
當然，在尾數進行加減法運算的時候，也可能會溢位，但是這種溢位可能是不致命的，常見的尾數溢位種類和處理手段如下所示：
- 尾數上溢：兩個同符號尾數相加產生了最高位向上的進位，要將尾數右移，階碼增\(1\)來重新對齊
- 尾數下溢：在將尾數右移時，尾數的最低有效位從尾數域右端流出，要進行舍入處理
5.2 浮點乘除法
? 浮點乘數法的計算程序比浮點加減法的計算程序從概念上來說簡單許多，大體上分為六個步驟：
- \(0\)運算元檢查
- 階碼加減操作
- 尾數乘除操作
- 結果規格化
- 舍入處理
- 確定積的符號
上面的步驟暗示出此處的尾數乘法實際上是按照原碼進行的（因為符號位單獨處理），也就是用到了2.5節中敘述的原理，當然，在此程序中也要時刻注意是否有溢位問題，浮點乘除法的整個流程如下圖所示：
參考資料
- 白中英，戴志濤，《計算機組成原理（第六版）》，科學出版社，2019
- 白中英，楊春武，《計算機組成原理：題解、題庫與試驗（第三版）》，科學出版社，2001
- 唐朔飛，《計算機組成原理（第二版）》，高等教育出版社，2008
- Randal E. Bryant, David R. O’Hallaron, Computer Systems - A Programmer’s Perspective 3 Edi Global Edition, Pearson, 2016
- David A. Patterson, John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface 5 Edi, Morgan Kaufmann, 2013
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/455604.html
標籤：其他
上一篇：什么是機器學習的特征工程？【資料集特征抽取（字典，文本TF-Idf）、特征預處理（標準化，歸一化）、特征降維（低方差，相關系數，PCA）】
下一篇：Docker快速入門(上)