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

文章出處

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

Encode　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

無符號整數只能表示大于或等于零的整數值。其二進制編碼方式十分直觀，僅包含真值域。

我們以8bit的存儲空間為例，真值域則占8bit，因此可表示的數值范圍是{0,...,255}，對應的二進制編碼是{00000000,...,11111111}。

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

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

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

Zero-extend　　　　　　　　　　　　　　　　　　　　　　　　　　

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

例如現在我們要將8bit的00000100擴展為16bit，那么我們只要將高8bit設置為0即得到000000000000000100，而其數值并不產生變化。

Truncation　　　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

Addition　　　　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

1. 算術加法；

2. 執行截斷操作。

示例，兩個4bit的無符號數相加(11+6)：

1011

+0110

10001，然后執行截斷得到0001

Subtraction　　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

2. 算術加法；

3. 執行截斷操作。

示例，兩個4bit的無符號數相減(11-6)：

1011

-0110

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

1011

+1010

10101，然后執行截斷得到0101

Multiplication　　　　　　　　　　　　　　　　　　　　　　　　

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

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

2. 對于乘數不為2的n次冪的情況

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

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

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

第一組：2<<(5+1) - 2<<5 = 64

第二組：2<<(3+1) - 2<<3 = 16

第三組：2<<(1+1) - 2<<0 = 6

相加得到86

2.4. 對結果取模。

Dividision　　　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

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

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

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

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

以下是C的實現：

#include <stdio.h>

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

int main(){
  // 輸入
  unsigned short dividend = 14, divisor = 5;
 
  // 輸出
  unsigned short quotients = 0,  // 商
                 rem = 0;        // 余數

  // 中間值
  unsigned short highest_bit_weight,
         divisor_aligned,
         tmp_dividend = dividend;
  unsigned short high_alignment;

  // 開始運算
  while (1){
      // 高位對齊 (從高位開始運算)
      // 結果：1. 要么被除數的最高位小于除數的最高位;
      //       2. 要么被除數的最高位對齊除數的最高位, 且被除數大于除數;
      high_alignment = 0;
      highest_bit_weight = lowest_bit_weight;
      divisor_aligned = 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("%u/%u=%u(rem:%u)\n", dividend, divisor, quotients, rem);
  return 0;
}