前言
◆ ◆ ◆ ◆
這期本來是想寫hashMap的，但是裡面哈希和擴容之類的，很多都是位運算，不太熟悉的同學看著會很難受，所以先補充一些計算機組成的知識。
進位轉換
◆ ◆ ◆ ◆
計算機中，二進位是最廣泛的一種數制，以高低電平來表示二進位。當數碼很大時，書寫不方便，從而引進八進位和十六進位，但是其實計算機內部都是二進位。
我們熟悉的十進位如何在計算機中表示呢，比如把十進位數19.6875轉化為二進位。
首先整數部分和小數部分需要分開來算。
整數部分：除2取餘，自下而上
19/2=9 餘1
9/2=4 餘1
4/2=2 餘0
2/2=1 餘0
1/2=0 餘1
（商為0為結束標誌）
所以餘數自下而上寫：10011
小數部分：乘2取整，自上而下
0.6875*2=1.375 取1 餘0.375
0.375*2=0.75 取0 餘0.75
0.75*2=1.5 取1 餘0.5
0.5*2=1 取1 餘0
（取1餘0為結束標誌）
所以自上而下表示：1011
綜上，19.6875的二進位表示為：10011.1011
真值和計算機數
◆ ◆ ◆ ◆
日常表示為+6、-8、-0.756這樣的數成為真值。但是計算機並不知道「+」，「-」。由於0、1正好為兩種狀態，於是就規定0表示正號，1表示負號，這樣被數位化的數就稱為計算機數
BCD碼
◆ ◆ ◆ ◆
二進位編碼的十進位數（Binary Coded Decimal,BCD）是以二進位數來編碼表示二進位0-9，分為兩類：有權BCD碼，如8421碼、2421碼、5421碼等；無權BCD碼，如餘3碼、格雷碼等
（1）8421碼：用四位二進位數表示一位十進位數，權值從高到低為8，4，2，1。如101001表示29
（2）餘3碼：8421碼的基礎上加上十進位3
定點數的表示
◆ ◆ ◆ ◆
無符號數表示：整個機器字長全部二進位均為數值，沒有符號為，相當於數的絕對值，如機器字長為8位，表示範圍為0-2^8-1，即0-255有符號數表示：0表示正號，1表示負號，一般為：原碼、補碼、反碼（1）3種機器數的最高位都為符號位（2）當真值為正數時，原碼、補碼、反碼的表示均相同，即符號位為0，數值部分和真值相同（3）當真值為負數時，符號位為1，數值部分，補碼是原碼的「每位求反加1」，反碼為原碼的「每位求反」。注意：僅數值部分，不包括符號如：+1110，原，補，反均為01110-1101，原碼：11101，補碼：10011，反碼：100100的原碼和反碼都有兩種，補碼只有一種表示範圍如下：
原碼：-（2^(n-1) -1）~ (2^(n-1) -1)
補碼：-2^(n-1) ~ (2^(n-1) -1)
反碼：-（2^(n-1) -1）~ (2^(n-1) -1)
移碼
◆ ◆ ◆ ◆
介紹一下補碼的缺點，舉個例子
從代碼形式上看，符號位也是一位二進位，將這些二進位代碼進行比較，會得出101011>010101,100001>011111，其實恰好相反，這就是補碼的缺點，但是可以通過移碼來彌補。
將每一個真值加上2^n,如例子中n為5，得到
這樣就能得到110101>001011,111111>000001
加上真值的過程其實就是移碼
是不是比較懵逼……
其實，移碼就是補碼的符號位取反
補碼的好處
◆ ◆ ◆ ◆
假設機器字長為4位，一位為符號，則補碼的範圍為-8~7，列出看一下
0000 0 1000 -8
0001 1 1001 -7
0010 2 1010 -6
0011 3 1011 -5
0100 4 1101 -4
0101 5 1101 -3
0110 6 1110 -2
0111 7 1111 -1
優點1：補碼的設計可以滿足x+(-x)=0，因為高位進位捨去；知道x的補碼，求-x的補碼，為：x的補碼連同符號位在內每位取反再加1。
優點2：0的補碼只有一種
優點3：補碼的符號位可以參與運算，不需要單獨設置電路
優點4：採用補碼運算後，補碼可以將正數加負數轉化為正數加正數，又可以將減法轉換為加法運算，這樣就只設加法器就可以了
優點5：補碼可以解決補碼數的擴充問題。因為在補碼表示中，全「1」代表-1，所以對負數補碼進行擴充，可以直接補符號位，如1001擴充為8位，可以寫為11111001；0111擴充為8位，可以寫為：00000111
所以大部分計算機系統都採用補碼來表示機器數
定點數的移位運算
◆ ◆ ◆ ◆
當某個二進位數相對於小數點做n位左移或者右移時，相當於該數乘以或者除以2的n次方。由於計算機中的機器字長都是固定的，當機器數左移或者右移時，都會使其n位低位或者n位高位出現空缺，就需要補0或者補1。需要考慮邏輯位移和算術位移。
（1）邏輯移位：邏輯左移時，高位移丟，低位補0；邏輯右移時，低位移丟，高位補0。如寄存器的內容為：10001010，邏輯左移為00010100，邏輯右移為01000101.
（2）算術移位：
<1>當機器數為正時，
1）原碼：左移右移都補0
2）補碼：左移右移都補0
3）反碼：左移右移都補0
<2>當機器數為負時，
1）原碼：左移右移都補0
2）補碼：左移補0右移補1
3）反碼：左移右移都補1
補碼定點數的加/減法運算
◆ ◆ ◆ ◆
（1）補碼加法：符號位參加運算，兩數和的補碼等於兩數的補碼之和，公式為
[x+y]補=[x]補+[y]補
（2）補碼減法：運算器只包含加法器，於是需要用到[y]補和[-y]補，公式為
[x-y]補=[x]補+[-y]補
加減法的溢出判斷
◆ ◆ ◆ ◆
（1）一位符號位判斷溢出：一個正數和一個負數相加是不會溢出的。參加運算的兩個數符號相同，其結果的符號可能與操作數不同，即為溢出，硬體實現判斷為：
最高有效位的進位異或符號位的進位=1
則為溢出
比如：兩個正數相加，符號位都是0，數值的最高位產生進位1，這個進位會進到符號位，符號位由0變成1且不會向上產生進位。所以最高有效位的進位=1，符號位進位=0，異或等於1，產生溢出。如果兩個操作數都是負數，如果數值的最高位向上沒有進位=0，因為符號位都是1，符號位向上進位=1，產生溢出。
（2）兩位符號位溢出判斷：雙符號位相同，則未溢出，雙符號位不同，則為溢出，最高符號位代表真正的符號。
補碼乘法一位乘
◆ ◆ ◆ ◆
被乘數與部分積一般取雙符號位，並且符號位參與運算。（原因：一旦產生溢出，單符號位會出錯，而雙符號位的最高位是正確的符號位）乘數取單符號位以決定最後一步是否需要校正，即是否加[-x]補乘數末尾增設附件位Y（n+1),初始值為0根據Yn和Y（n+1）判斷位，進行運算，步驟同上根據上述算法進行n+1步，但是第n+1步不再移位，僅根據Y0,Y1比較結果決定是否要加[x]補按補碼移位規則，即部分積為正時，右移過程中有效位最高位補0；部分積為負時，右移過程中有效位最高位補1；雙符號的移位中，次高符號位參與移位，最高位不參與針對第四步，給出下列規則表
是不是很懵，用一個例子來看一下：
已知[x]補=1.0101，[y]補=1.0011，求[xy]補
解：先求[-x]補=0.1011,詳細過程如下
看懂表格可能就了解得差不多了。如果看不懂，可以加小明同學聊聊。
算數邏輯單元ALU
◆ ◆ ◆ ◆
數字電路一般可分為組合邏輯電路和時序邏輯電路。
組合邏輯電路：在邏輯功能上的特點是任意時刻的輸出僅僅取決於該時刻的輸入，與電路原來的狀態無關。也就是說，組合邏輯電路沒有記憶功能，運算後的結果要立刻送入寄存器保存時序邏輯電路：在邏輯功能上的特點是任意時刻的輸出不僅取決於當時的輸入信號，還取決於電路原來的狀態。也就是說，時序邏輯電路具有記憶元件，即觸發器（能夠存儲一位信號的基本單元電路），可以記錄前一時刻的輸出狀態。ALU是一種組合邏輯電路，因此實際使用ALU時，其輸入埠A和B必須與鎖存器相連，而且運算過程中鎖存器（多位觸發器）的內容是不變的，其輸出必須送至寄存器保存。
ALU主要功能：ALU的功能不僅僅是執行算術（加、減、乘、除）和邏輯運算（與，或，非，異或）的部件，還具有先行進位邏輯。在並行加法器的並行進位鏈就是使用ALU。
下圖就是ALU的電路框架
其中A，B為輸入變量，K為控制信號，K的不同取值可以決定該電路進行哪一種算數運算或哪一種邏輯運算，F為輸出
串行加法器
◆ ◆ ◆ ◆
首先介紹一下全加器。全機器是一個加法單元，而一個加法單元是一個三端輸入、兩端輸入的加法網絡，如圖所示
其中Ai代表被加數，Bi代表加數，Ci-1代表低位穿來的進位，Ci代表本位向高位的進位，和為Si
只設一個全加器的加法器稱為串行加法器。兩個操作數分別放到兩個移位寄存器中，並且由移位寄存器從低位到高位串行地提供操作數進行相加。如果操作數長16位，就需要分成16步進行，每步產生一為和，串行地送入結果寄存器，而產生的進位信號只需要一位觸發器，每完成一步，用新的進位覆蓋舊的進位。串行加法器的結構如下圖
所得的結果保存在操作數A的寄存器中，但是每次都是一位參與運算，速度太慢。如果操作數長16位，就需要分成16步進行，這是不可接受的。於是就有並行加法器
並行加法器
◆ ◆ ◆ ◆
由n+1個全加器構成的並行加法器，這樣兩個n+1位的數可以利用這個加法器並行計算。
對於每一個全加器，有三個輸入，其中兩個輸入對應了參與運算的兩個數的響應位，另一個輸入是低位的進位。有兩個輸出，一個輸出是對應的加法和的結果對應位，另一個輸出是本地產生的向高位的進位
每個全加器的結果Si是如何產生的呢？
Si指出了運算結果某一位到底是1還是0.如果輸入的三位都是1或者其中一位是1，另外兩個是0，對應的Si就為1，表達式為
這個表達式中，A和B都是參與運算的數據，保存在寄存器中，但是Ci-1是由低位產生的進位，只有這個進位產生後，才能計算出Si。所以影響速率就是Ci-1的產生。
那進位C是如何產生的呢？
如果三個輸入都是1，或者兩個輸入是1，一個輸入是0，就會產生進位，表示為
我們把AiBi叫做本地進位，也就是本地參與運算的兩個數據響應的位就會產生的進位。另外Ai+Bi表示傳送條件，用ti表示。如果這個或的值為1，那麼Ci-1的結果就會被傳送到Ci。所以我們就知道進位也可以由輸入的Ai和Bi知道，所以就能快速產生進位了。
我們記AiBi為di，則進位表示如下
串行進位鏈
◆ ◆ ◆ ◆
進位鏈：傳送進位的電路。也就是說在加法器中，我們可以把進位產生的電路獨立出來，產生進位以後相應的進位再和AiBi一起參與運算生成Si。
我們以4位全加器為例，則每一位的進位表達式為
為了使用與非門實現進位鏈，對上面表達式進行變換，則
根據表達式，得出通過與非門產生的串行進位鏈：每個進位的產生需要採用兩個與非門。如C0為例，根據變換的結果，使用t0和C-1的與操作，再做非操作輸出，之後用d0的非和之前得到的結果再做與操作，非操作，就可以得到C0。這樣我們就可以依次得到如下串行進位鏈。
並行進位鏈
◆ ◆ ◆ ◆
串行加法還是太慢了怎麼辦呢，這樣就可以考慮是不是可以並行輸出，讓n位的加法器的進位同時產生。
首先對串行進位鏈中得到的表達式再進行變換得到如下
回顧一下，ti=AiBi,di=Ai+Bi
這樣我們就可以由每一位參與運算的的位直接得出了所有進位了！這種稱為並行進位或者跳躍進位。
單重分組跳躍進位鏈
◆ ◆ ◆ ◆
上圖的跳躍進位的電路很複雜，而且才4位數。如果是32位或者64位，則會非常龐大而且複雜。為此又產生了兩種折中的跳躍進位鏈。
n位全加器分成若干個小組，每個小組中的進位同時產生，小組之間串行進位。
以16位為例子
上圖中，組和組之間採用串行進位，也就是說當第四組中的C3產生以後，把C3作為輸入輸入到第三組中，這個C3和第三組中的di，ti配合，生成第三組中的所有Ci，同樣第二組，第一組同理。
雙重分組跳躍進位鏈
◆ ◆ ◆ ◆
n 位全加器分若干大組，大組中又包含若干小組。每個大組中小組的最高位進位同時產生。大組與大組之間採用串行進位。
上圖中，將32為分成2個大組，每個大組中分為四個小組，每個小組中四位。C3，C7，C11，C15對應了，8，7，6，5，四個小組的最高位的進位，這四個進位同時產生。同樣，對第一大組來說C19，C23，C27，C31對應了4,3,2,1四個小組中的最高位進位，這四位進位也是同時產生。另外大組和大組之間採用串行進位的方式，也就是C15產生之後，作為輸入，輸入到第一大組中，用以產生第一大組中每個小組的最高位的進位和其他的進位。
看完這些，考研都夠用了~
◆ ◆ ◆ ◆
- end -
祝各位人人都能漲20K！
每個人都是技術大牛！
- TEN END -