Foundations of Computer Science Chapter 4 資料運算 計算機概論 第二版 Foundations of Computer Science Chapter 4 資料運算

4.1 邏輯運算 邏輯運算（logic operations）是指那些應用相同基本運算於一個樣式中個別的位元或兩個樣式中兩個相對應的位元之運算，可以定義邏輯運算於位元階層或樣式階層。 位元階層之邏輯運算 四種位元階層的運算用來操作位元：NOT、AND、OR 及XOR。 真值表（truth table）定義了各種可能輸入或輸入組合的輸出值。 p.74

圖 4.1 位元階層之邏輯運算 p.74

AND 運算子（AND operator）是一個二元運算子：如果兩個輸入皆為 1，則輸出值為 1，在其他三種情形中，輸出值為0。 NOT NOT 運算子（NOT operator）是一個一元運算子：如果輸入為 0，則輸出為 1，如果輸入為 1，則輸出為 0。換言之，NOT 運算子反轉其輸入值。 AND AND 運算子（AND operator）是一個二元運算子：如果兩個輸入皆為 1，則輸出值為 1，在其他三種情形中，輸出值為0。 AND 運算子有趣的一點是如果輸入位元有一個為 0，其結果為 0。 對 x = 0 或 1 x AND 0 → 0 且 0 AND x → 0 p.75

OR 運算子（OR operator）也是一個二元運算子：如果兩個輸入皆為 0，則輸出值為 0，在其他三種情形中，輸出值為 1。 對 x = 0 或 1 x OR 1 → 1 且 1 OR x → 1 p.75

對 x = 0 或 1 1 XOR x → NOT x 且 x XOR 1 → NOT x XOR 運算子（XOR operator，念為 exclusive-or：互斥或）：如果兩個輸入皆為 1，則輸出值為 0；而兩個輸入不同時，輸出值為 1。 XOR 的一個性質是如果輸入的一個位元為 1，其結果為另一個輸入相對應的位元之補數。 對 x = 0 或 1 1 XOR x → NOT x 且 x XOR 1 → NOT x p.75

範例 4.1 在英文中，我們使用連接詞「或」有時表示是相容或，而有時表 示是互斥或。 a. 句子「我希望有一輛車子或一棟房子」使用的「或」是「相容 或」的意義──我希望有一輛車子、一棟房子或兩者都有。 b. 句子「今天是星期一或星期二」使用的「或」是「互斥或」的 意義──今天是星期一或星期二，但不可能兩者都是。 p.75

x XOR y ↔ [x AND (NOT y)] OR [(NOT x) AND y] 範例 4.2 XOR 運算子實際上並不是一個新的運算子，我們永遠可以用其他 三個運算子來模擬它。下面兩個運算式是相等的。 如果我們求出這兩個運算式的真值表，就可以證明這個等式。 x XOR y ↔ [x AND (NOT y)] OR [(NOT x) AND y] p.76

樣式階層之位元運算 這相同四個運算子（NOT、AND、OR 和 XOR）可以應用於 n 位元的樣式中，其結果如同應用每一個運算子至每一個獨立位元如 NOT，與每一對相對應的位元如其他三個運算子。 圖 4.2 應用至位元樣式的邏輯運算子 p.76

範例 4.3 使用 NOT 運算子於位元樣式 10011000。 解答 答案如下。注意 NOT 運算子改變每一個 0 為 1 及每一個 1 為 0。 p.76

範例 4.4 使用 AND 運算子於位元樣式 10011000 和 00101010。 解答 答案如下。注意在輸出中只有一個位元為 1，其相對應的兩個輸入 皆為 1。 p.77

範例 4.5 使用 OR 運算子於位元樣式 10011001 和 00101110。 解答 答案如下。注意在輸出中只有一個位元為 0，其相對應的兩個輸入 皆為 0。 p.77

範例 4.6 使用 XOR 運算子於位元樣式 10011001 和 00101110。 解答 答案如下。比較本例與範例 4.5 的輸出，唯一的不同在於當兩個輸 入皆為 1 時，其結果為 0（互斥的結果）。 p.77

NOT 運算子唯一的應用就是對整個樣式取補數。 清除特定位元 有四種邏輯運算可用來修改位元樣式。 取補數 NOT 運算子唯一的應用就是對整個樣式取補數。 清除特定位元 AND 運算子的應用之一就是清除（unset，強迫為 0）一個位元樣式中的特定位元。在這情況中第二個輸入稱為遮罩（mask），在遮罩中為 0 的位元會清除第一個輸入中相對應的位元；在遮罩中為 1 的位元會保留第一個輸入中相對應的位元不變。 p.77

範例 4.7 使用一個遮罩來清除一樣式最左邊 5 個位元，用樣式 10100110 測 試此遮罩。 解答 遮罩為 00000111，應用此遮罩的結果為： 注意最右邊三個位元保持不變，而最左邊五個位元被清除（改變 為 0），而不管它們舊值為何。 p.78

設定特定位元 OR 運算子的應用之一就是設定（set，強迫為 1）一個位元樣式中的特定位元。同樣地我們可以利用一個不同的遮罩，在遮罩中為 1 的位元會設定第一個輸入中相對應的位元；在遮罩中為 0 的位元會保留第一個輸入中相對應的位元不變。 反轉特定位元 XOR 運算子的應用之一就是反轉（取補數）一個位元樣式中的特定位元。同樣地我們可以利用一個不同的遮罩，在遮罩中為 1 的位元會反轉第一個輸入中相對應的位元；在遮罩中為 0 的位元會保留第一個輸入中相對應的位元不變。 p.78

範例 4.8 使用一個遮罩設定一樣式最左邊 5 個位元，用樣式 10100110 測試 此遮罩。 解答 遮罩為 11111000，應用此遮罩的結果為： p.78

範例 4.9 使用一個遮罩反轉一樣式最左邊 5 個位元，用樣式 10100110 測試 此遮罩。 解答 遮罩為 11111000，應用此遮罩的結果為： p.79

4.2 移位運算 移位運算移動一個樣式中的位元來改變位元的位置，這些運算可以將位元往左移或往右移。我們可以將移位運算區分為兩類：邏輯移位運算與算術移位運算。 邏輯移位運算 邏輯移位運算（logical shift operation）是應用於一個不是有號數值的樣式，可區分為兩類。 邏輯移位 邏輯右移運算將每個位元往右移動一個位置。最右邊的位元被丟棄而最左邊位元填入 0，邏輯左移運算將每個位元往左移動一個位置。最左邊的位元被丟棄而最右邊位元填入 0。 p.79

圖 4.3 邏輯移位運算 p.80

範例 4.10 使用邏輯左移運算於位元樣式 10011000。 解答 答案如下。最左邊位元被丟棄且插入 0 做為最右邊的位元。 p.80

循環移位運算 循環移位運算〔circular shift operation；或旋轉運算（rotate operation）〕移動位元，但是不丟棄位元或增加位元。循環右移運算（右旋）向右移動每個位元一個位置，最右邊的位元被循環成為最左邊的位元。循環左移運算（左旋）向左移動每個位元一個位置，最左邊的位元被循環成為最右邊的位元。 p.80

圖 4.4 循環移位運算 p.80

範例 4.11 使用循環左移運算於位元樣式 10011000。 解答 答案如下。最左邊位元被丟棄且插入 0 做為最右邊的位元。 p.80

算術移位運算 算術移位運算（arithmetic shift operations）假設位元樣式是一個 2 補數格式的有號整數。算術右移是用來將一整數除以 2，而算術左移是用來將一整數乘 2，這些運算不應該改變其符號（最左邊）位元。算術右移保留其符號位元，但也複製符號位元至其右邊下一個位元。算術左移丟棄其符號位元，並接受符號位元左邊的位元作為符號位元。如果新的符號位元與之前的符號相同，表示此運算是成功的，否則就會發生溢位或下限溢位而且結果是無效的。 p.81

圖 4.5 算術移位運算 p.81

範例 4.12 使用算術右移運算於位元樣式 10011001，此樣式為 2 補數格式之 整數。 解答 答案如下。最左邊位元被保留且複製至其右邊相鄰的位元。 原來的數值為 –103 而新的數值為 –52，這是 –103 除以 2 且捨棄尾 數成為較小整數的結果。 p.81

範例 4.13 使用算術左移運算於位元樣式 11011001，此樣式為 2 補數格式之 整數。 解答 答案如下。最左邊位元被丟棄且插入 0 做為最右邊的位元。 原來的數值為 –39 而新的數值為 –78，原來的數值乘 2。這個運算 是有效的，因為沒有發生下限溢位。 p.81

範例 4.14 使用算術左移運算於位元樣式 01111111。此樣式為 2 補數格式之 整數。 解答 答案如下。最左邊位元被丟棄且插入 0 做為最右邊的位元。 原來的數值為 127 而新的數值為 –2。這結果是無效的，因為發生 溢位。原先所預期的答案 127 × 2 = 254 無法用一個 8 位元的樣式 來表達。 p.82

範例 4.15 結合邏輯運算及邏輯移位運算可提供給我們一些操作位元樣式的 工具，假設我們有一個樣式而且在一個決策過程中需要利用這個 樣式的第三個位元（從右邊數起），我們想要知道這個特別的位 元是 0 或 1，下面步驟顯示我們如何查知。 p.82

A – B ↔ A + (B+1) 其中 ((B+1)) 表示 B 的 2 補數 4.3 算術運算 算術運算（arithmetic operations）牽涉了加法、減法、乘法和除法，可應用到整數與浮點數。 2 補數表示法的整數之加法和減法，整數通常是儲存成 2 補數格式。當遇到減法運算時，電腦簡單地將它改變成加法運算，但是將第二個數值取 2 補數。 A – B ↔ A + (B+1) 其中 ((B+1)) 表示 B 的 2 補數 我們用記號（X ＋ 1）來表示 X 的 2 補數，此程序如下： 1. 如果是減法運算，則取第二個整數的 2 補數，否則進入下一步驟。 2. 兩個整數相加。 p.82

表 4.1 兩個位元相加之進位與總和的結果 p.83

範例 4.16 兩個整數 A 和 B 儲存成 2 補數格式，顯示如何 A 加 B。 解答 此運算為加法，A 加 B 且結果儲存在 R 中。 我們檢查十進位之結果：(+17) + (+22) = (+39)。 A = (00010001)2 B = (00010110)2 進位 p.83

圖 4.6 2 補數格式之整數的加法與減法 p.84

範例 4.17 兩個整數 A 和 B 儲存成 2 補數格式，顯示如何 A 加 B。 解答 此運算為加法，A 加 B 且結果儲存在 R 中。 檢查十進位之結果：(+24) + (−17) = (+7)。 進位 p.84

範例 4.18 兩個整數 A 和 B 儲存成 2 補數格式，顯示如何 A 減 B。 解答 此運算為減法，A 加 (B+1) 且結果儲存在 R 中。 檢查十進位之結果：(+24) − (−17) = (+41)。 進位 p.85

範例 4.19 兩個整數 A 和 B 儲存成 2 補數格式，顯示如何 A 減 B。 解答 此運算為減法，A 加 (B+1) 且結果儲存在 R 中。 注意最後進位被捨棄。檢查十進位之結果：(−35) − (+20) = (−55)。 進位 p.85

範例 4.20 兩個整數 A 和 B 儲存成 2 補數格式，顯示如何 A 加 B。 解答 此運算為加法，A 加 B 且結果儲存在 R 中。 我們預期結果應該為 127 + 3 = 130，但是答案卻為 −126。這個錯 誤是由於溢位所造成，因為預期的答案 (+130) 不在 −128 至 +127 的範圍內。 進位 p.85

1. 檢查此運算。若是減法運算，則改變第二個整數（B）的符號。 2. 對這兩個整數的符號作 XOR 運算，若結果為 0，則表示符號相 同。 符號大小整數之加法或減法 符號大小表示法之整數的加法或減法看起來非常複雜。加法有四種不同的符號組合（兩個符號，各有兩個值），而減法有四種不同的狀況，這表示需要考慮八種不同的情況。但是，如果我們先檢查符號，則可以減少這些情況。 1. 檢查此運算。若是減法運算，則改變第二個整數（B）的符號。 2. 對這兩個整數的符號作 XOR 運算，若結果為 0，則表示符號相 同。 當我們在電腦中執行數值的算術運算時，應該要記住每個數值與結果必須落在位元配置所定義的大小範圍內。 p.86

3. 如果符號相同，R = ±(AM + BM)。我們需要將大小相加而且結果 的符號就是共同的符號。 RM = (AM) + (BM)　　且　　RS = AS 在此情況下我們應該要注意溢位問題。當兩個數值相加時，可 能會產生溢位必須加以回報並且中止此程序。 4. 如果符號不同，R = ±(AM － BM)，將 AM 減去 BM 然後決定符 號。取第二個數值（BM）的 2 補數然後相加，結果的符號是較 大整數的符號。 可以看出如果 AM ≥ BM，則會有溢位，而且結果是個正數。因此如果有溢位，則捨棄溢位，並且將結果的符號設為 A 的符號。 可以看出如果 AM < BM，則沒有溢位，但結果是個負數。因此如果沒有溢位，則取結果之 2 補數，並且將結果的符號設為 B 的符號。 p.86

圖 4.7 符號大小格式之整數的加法和減法 p.87

範例 4.21 兩個整數 A 和 B 儲存成符號大小格式。顯示如何 A 加 B。 解答 此運算為加法：B 的符號不變，因為 S = AS XOR BS = 0，RM = AM + BM 且 RS = AS，沒有溢位。檢查十進位之結果：(+17) + (+22) = (+39)。 p.87

範例 4.22 兩個整數 A 和 B 儲存成符號大小格式，顯示如何 A 加 B。 解答 此運算為加法：B 的符號不變。因為 S = AS XOR BS = 1；RM = AM + (BM + 1)。因為沒有溢位，所以要取 RM 的 2 補數，R 的符號是 B 的符號。檢查十進位之結果：(+17) + (−22) = (−5)。 p.88

範例 4.23 兩個整數 A 和 B 儲存成符號大小格式。顯示如何 A 減 B。 解答 此運算為減法：BS = BS。S = AS XOR BS = 1，RM = AM + (BM + 1)。因為有溢位，所以 RM 的值就是最後結果，R 的符號是 A 的符 號。檢查十進位之結果：(−18) − (−22) = (−59)。 p.88

所有的算術運算如加法、減法、乘法與除法都可以應用在儲存成浮點數格式之實數。 實數的算術運算 所有的算術運算如加法、減法、乘法與除法都可以應用在儲存成浮點數格式之實數。 以浮點數儲存之實數的加法與減法可以簡化成兩個經過小數點對齊後之符號大小（符號與大小之組合）整數的加法與減法。簡化的過程如下： 1. 如果兩個數值（A 或 B）中任一個為 0，則結果為 0 並停止。 2. 如果是減法運算，改變第二個數值（B）的符號以便於模擬成加法。 p.88

圖 4.8 浮點數格式之實數的加法與減法 p.89

3. 反正規化這兩個數值，將隱藏的 1 包含至尾數中與遞增指數，此時尾數可視為是一個整數。 4. 然後對齊指數，這表示遞增較小的指數並移動相對應的尾數，直到兩個指數相等。例如，如果： 1.11101 × 24 + 1.01 × 22 必須使兩個指數為 4： 1.11101 × 24 + 0.0101 × 24 5. 現在，我們可將每個數值的符號與大小之組合視為一個符號大小格式的整數，然後將兩個整數相加。 6. 最後，再次正規化此數值成為 1.000111 × 25。 p.90

範例 4.24 顯示電腦如何求得 (+5.75) + (+161.875) = (+167.625) 之結果。 解答 每個數字都有一個隱藏的 1。 直接移至反正規化步驟並且將尾數加上隱藏的 1 來加以反正規化 此數值，以及遞增指數，此時兩個反正規化後的尾數長度是 24 位 元並且包含了隱藏的 1。 p.90

要對齊尾數，必須遞增第一個指數並將尾數向右移位。 做符號大小法之加法。 尾數沒有發生溢位，所以做正規化。 p.91

尾數只有 23 個位元不需要做捨棄。 E = (10000110)2 = 134 ，M = 0100111101 。 此結果為 (1.0100111101)2 × 2134 – 127 = (10100111.101)2 = 167.625。 p.91

範例 4.25 顯示電腦如何求得 (+5.75) + (–7.0234375) = –1.2734375 之結果。 解答 這兩個儲存為浮點數格式之數值，如下所示： 反正規化的結果為： p.91

不需要對齊（因為兩個指數相同），應用加法運算於符號與大小 之組合。結果顯示如下，其中結果的符號為負： 現在需要做正規化： 尾數現在是24 個位元，捨去成為23 個位元。 結果為 R = –2127 – 127 × 1.0100011 = –1.2734375，正如所預期一樣。 p.92