基礎野：細說有符號整數 - fsjohnhuang－IT工程師數位筆記本

文章出處

Breif　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

本來只打算理解JS中0.1 + 0.2 == 0.30000000000000004的原因，但發現自己對計算機的數字表示和運算十分陌生，于是只好惡補一下。

本篇我們一起來探討一下基礎——有符號整數的表示方式和加減乘除運算。

Encode　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

有符號整數可表示正整數、0和負整數值。其二進制編碼方式包含符號位和真值域。

我們以8bit的存儲空間為例，最左1bit為符號位，而其余7bit為真值域，因此可表示的數值范圍是{-128,...,127}，對應的二進制補碼編碼是{10000000,...,01111111}。

從集合論的角度描述，我們可以將十進制表示的數值范圍定義為集合A，將二進制表示的數值范圍定義為集合B，他們之間的映射為f。f(a)=b，其中a屬于A、b屬于B。并且f為雙射函數。因此有符號整數表示方式具有如下特點：

1. 可表示的數值范圍小；

2. 十進制表示的數值范圍與二進制表示的數值范圍的元素是一一對應的，兩者可精確映射轉換。（相對浮點數而言，某些二進制表示的數值只能映射為十進制表示的數值的近似值而已）；

3. C語言中雖然沒有規定必須采用補碼來對有符號數進行編碼，但大部分實現均是采用補碼。而Java和C#則明確規定采用補碼來表示有符號數。

Sign-extended　　　　　　　　　　　　　　　　　　　　　　　　

符號擴展運算用于在保持數值不變、符號位不變的前提下，不同字長的整數之間的轉換。

例如現在我們要將8bit的10000100擴展為16bit，那么我們只要將高8bit設置為與原來符號位相同的值（這里是1）即得到1111111110000100，而其數值和符號并不產生變化。

Truncation　　　　　　　　　　　　　　　　　　　　　　　　　　

截斷會減少位數，并對原始值取模。模為2^n，n為截斷后的位數。

例如現在將16bit的100000100000000100截斷為8bit，那么結果為00000100，而模是2^8。

Addition　　　　　　　　　　　　　　　　　　　　　　　　　　　　

注意：位級運算均是模數運算，即加減乘除后均會對運算結果取模，并以取模后的結果作為終止返回。

有符號整數加法的運算順序：

1. 算術加法（由于采用補碼對有符號數進行編碼，則是已經將負數轉換為正數存儲，所以含負數的加法只需要直接執行算術加法即可）；

2. 執行截斷操作。

示例1，兩個4bit的有符號數相加(3+6)：

0011

+0110

1001，然后執行截斷得到1001，發生正溢出得到 -7

示例2，兩個4bit的有符號數相加(-3+6)：

1101

+0110

10011，然后執行截斷得到0011，發生正溢出得到 3

Subtraction　　　　　　　　　　　　　　　　　　　　　　　　　　

有符號整數減法的運算順序：

1. 將減法轉換為加法（對減數取補碼）；

2. 算術加法；

3. 執行截斷操作。

示例1，兩個4bit的有符號數相減(-5-6)：

1011

-0110

對減數求補碼后，減法轉換為加法

1011

+1010

10101，然后執行截斷得到0101，發生負溢出得到5

示例2，兩個4bit的有符號數相減(-5-(-6))：

1011

-1010

對減數求補碼后，減法轉換為加法

1011

+0110

10001，然后執行截斷得到0001，得到1

Multiplication　　　　　　　　　　　　　　　　　　　　　　　　　

對于乘法實質上就是通過移位操作和加、減法組合而成。

1. 將乘數以二進制形式表示，并以連續的1作為分組。如-5的二進制形式為(1)0(11)，從左至右可分成2組分別是(1)、(11)。

2. 以n表示每組的最高位的指數，以m表示每組最低位的指數。如第一組n=m=3，第二組n=1而m=0。

3. 根據公式(x<<n+1)-(x<<m)對每組進行運算，并將結果相加。如(假設被乘數為-1)

第一組：(1111)<<(3+1) - (1111)<<3 = 0000 - 1000 = 0000 + 1000 = 1000

第二組：(1111)<<(1+1) - (1111)<<0 = 1100 - 1111 = 1100 + 0001 = 1101

兩組相加：1000 + 1101 = 10101，截斷得到0101，等于十進制數值5.

2.4. 對結果取模。

Division　　　　　　　　　　　　　　　　　　　　　　　　　　　　

對于除法實質上就是通過移位操作和加、減法組合而成，且根據除數是否為2的n次冪(n為正數)區別處理。

1. 對于被除數為2的n次冪(n為正數)的情況，除法公式為：a>>n，如-6/4等價于6/(2^2)，則可轉換為移位操作-6>>2即可。然后再對結果取模。

2. 對于被除數不為2的n次冪(n為正數)的情況，則情況復雜不少。運算步驟如下：（實質上我們就是按這個步驟做十進制除法的）

　　 2.1. 對負數取補，提取符號乘積。

2.2. 高位對齊，在除數值小于被除數值的前提下，讓除數的位數等于被除數；若執行高位對齊后，除數值大于被除數時，則除數右移一位。得到位移數。

2.3. 試商，除數-被除數*N = 余數中間值，其中N*被除數 <= 除數 && （N+1）*被除數 > 除數。商 = 商 + N * 基數^位移數。

2.4. 循環執行上述步驟，直到無需再執行高位對齊，那么2.2中得到的余數中間值將作為除法運算的最終余數，否則余數中間值則作為一下輪高位對齊的被除數處理。

2.5. 符號乘積乘以商得到最終商，符號乘積乘以余數得到最終余數。

C語言實現：

#include <stdio.h>

// 前置條件
const char lowest_bit_weight = 1; // 二進制最低位的位權重

int main(){
  // 輸入
  char dividend = -5, divisor = -2;
 
  // 輸出
  char quotients = 0,  // 商
    rem = 0;        // 余數

  // 中間值
  char highest_bit_weight,
       divisor_aligned,
       tmp_dividend = dividend,
       tmp_divisor = divisor;
  char high_alignment;
  char sign,
       sign1 = 1,
       sign2 = 1;
 
  // 負數轉換為正數, 求符號乘積
  if (tmp_dividend < 0){
    tmp_dividend = ~tmp_dividend;
    tmp_dividend += 1;
    sign1 = ~sign1;
    sign1 += 1;
  }
  if (tmp_divisor < 0){
    tmp_divisor = ~tmp_divisor;
    tmp_divisor += 1;
    sign2 = ~sign2;
    sign2 += 1;
  }
  sign = sign1 * sign2; 


  // 開始運算
  while (1){
      // 高位對齊 (從高位開始運算)
      // 結果：1. 要么被除數的最高位小于除數的最高位;
      //       2. 要么被除數的最高位對齊除數的最高位, 且被除數大于除數;
          high_alignment = 0;
          highest_bit_weight = lowest_bit_weight;
      divisor_aligned = tmp_divisor;
      while (tmp_dividend >= divisor_aligned){
        divisor_aligned = divisor_aligned << 1;
        highest_bit_weight = highest_bit_weight << 1;

            high_alignment += 1;
      }
      if (high_alignment > 0){
        divisor_aligned = divisor_aligned >> 1;
        highest_bit_weight = highest_bit_weight >> 1;
            high_alignment -= 1;
          }

          // 當無需執行高位對齊時，則將下一輪的被除數作為余數，并且結束運算
          if (0 == high_alignment) {
        rem = tmp_dividend;
        break;
      }

      // 上一輪運算的商加上最高位權重得到當前運算的商值
      quotients = quotients | highest_bit_weight;
      // 被除數減除數的差值作下一輪的被除數
      tmp_dividend = tmp_dividend - divisor_aligned;
  }
  // 商*符號乘積 = 最終商，余數*符號乘積 = 最終余數
  printf("%d/%d=%d(rem:%d)\n", dividend, divisor, quotients * sign, rem * sign);
  return 0;
}