文章出處

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

  說來慚愧雖然剛接觸計算機時已經學過原碼、反碼和補碼的內容，但最近重溫時卻發現“這是什么鬼東西”，看來當初只是應付了考試了而已。本篇將試圖把他們說個明白，以防日后自己又忘記了。

  在深入之前，我們先明確以下幾點：

  1. 本篇內容全部針對有符號數整數；

  2. 對于有符號數整數，其在計算機中的存儲結構是 符號位 + 真值域。其中符號位為0表示正數，1表示負數；

  3. Q：既然已經有原碼，那么為什么還要出現反碼、補碼等數值的編碼方式呢？

      A：由于為了降低當時計算機物理電路的設計難度，決定采用加法代替減法運算（因此計算機內部是沒有減法運算的），即10-5被替換為10+(-5)，而反碼、補碼就用于解決10+(-5)的問題的。

 

True Form　　　　　　　　　　　　　　　　　　　　　　　　　　

  原碼(稱為true form、sign-magnitude 或 sign and magnitude)，就是直接將十進制數轉換為二進制數形式。如7的原碼為0111，-6的原碼為1110。

  注意：

  1. 原碼是區分+0和-0的，+0的原碼為0000;-0的原碼為1000；

  2. 若存儲空間為n bit，則原碼的取值范圍是 -2n-1 ~ 2n-1。

  原碼在以加法代替減法的運算中引起的問題：

        例如在計算0 = 1-1 = 1+(-1) = 0001 + 1001 = 1010 = -2， 發現通過原碼來運算時居然會得到0 == -2的結果。于是引入了反碼。

  一般用于IEEE 754浮點數標準中尾數(significant)的表示。

 

Ones' Complement　　　　　　　　　　　　　　　　　　　　　　

  原碼轉換成反碼的規則如下：

  　　1. 正整數原碼的反碼是其自身。如原碼0001的反碼是0001；

  　　2. 負整數原碼的反碼則是對原碼真值域的個位數取反即可。如原碼1010的反碼是1101。

  那么將反碼轉換為原碼的規則如下：

　　  1. 正整數反碼的反碼是其自身。如反碼0001的原碼是0001；  　　

　　  2. 負整數反碼的原碼則是對反碼真值域的個位數取反即可。如反碼1101的原碼是1010。

  注意：

  1. 反碼是區分+0和-0的，+0的反碼為0111;-0的反碼為1111；

  2. 若存儲空間為n bit，則反碼的取值范圍是 -2n-1 ~ 2n-1。

  反碼在以加法代替減法的運算中引起的問題：
        例如在計算0 = 1-1 = 1+(-1) = 0001【原碼】 + 1001【原碼】 = 0001【反碼】 + 1110【反碼】= 1111【反碼】 = 1000【原碼】 = -0， 發現通過反碼來運算時居然會得到0 == -0的結果。

        看到采用反碼運算的結果已經非常接近正確結果，但-0對于我們來說還是沒有太多的意義。于是引入了補碼。

 

Two's Complement　　　　　　　　　　　　　　　　　　　　　　

  原碼轉換成補碼的規則如下：

  　　1. 正整數原碼的補碼是其自身。如原碼0001的補碼是0001；

  　　2. 負整數原碼的補碼則是對原碼真值域的個位數取反后，整體+1即可。如原碼1010的補碼是1110。

  那么將補碼轉換為原碼的規則如下：

　　  1. 對補碼再求一次補碼則得到原碼。

  取補碼的流程發生在符號變化時，也就是正、負數間轉換。如-(1),-(-1)等。

  具體流程如下：

    1. 符號位取反；

    2. 真值域取反；

    3. 整體+1。

  因此在進行-(1)運算時，步驟如下（1的補碼是0001）：

    1. 符號位取反——1001

    2. 真值域取反——1110

    3. 整體+1——1111

    或將步驟1和2合并為對各位取反——1110，然后整體+1——1111

  在進行-(-1)運算時，步驟如下（-1的補碼是1111）：

    1. 符號位取反——0111

    2. 真值域取反——1000

    3. 整體+1——1001

    或將步驟1和2合并為對各位取反——1000，然后整體+1——1001

  注意：

  1. 補碼是不區分+0和-0的，+0和-0的補碼為0000;

  2. 若存儲空間為n bit，則反碼的取值范圍是 -2n ~ 2n-1。

  3. 原碼  + 其補碼 = 0。

  補碼在以加法代替減法的運算的結果：

  例如在計算0 = 1-1 = 1+(-1) = 0001【原碼】 + 1001【原碼】 = 0001【反碼】 + 1110【反碼】= 0001【補碼】+ 1111【補碼】 = 0000【補碼】 = 0000【原碼】=0， 發現通過補碼來運算時結果恰恰正確。

  真相：有符號整數其實是以補碼的編碼方式存儲的。因此C語言的int類型在32位OS上的值范圍是：-2n ~ 2n-1。我們可以通過以下的C代碼片段要驗證：

#include <stdout.h>
#include <string.h>

int main(){
  int f = -1;
  unsigned long l;
  int i;
  char s[32];

  memcpy(&l, &f, 4);

  for (i = 31; i >=0; --i){
       if (l % 2 == 1){
         s[i] = '1';
       }
       else{
         s[i] = '0';
       }
       l /= 2;
  }
  s[32] = '\0';
  printf("%s\n", s);
  return 0;
}

  標準輸出為：11111111111111111111111111111111（若為原碼則應該是10000000000000000000000000001）

  到這里我們對原碼、反碼和補碼有一定程度的了解，并通過死記硬背的傳統學習方法答對考題應該就不成問題了。但若要自圓其說則不可避免地需要解答以下問題：

  1. 為什么補碼的方式能解決以加法替代減法時所產生的問題？

  下面我們一起來探討和推導一下吧。

 

Theory　　　　　　　　　　　　　　　　　　　　　　　　　　　　

  Modulus

　   模，是指一個計量系統的計數范圍，而模則是產生“溢出”的量。

      以時鐘為例，時鐘的計數范圍是0~11，而模（產生“溢出”的量）是12。現在我們將時針從4點逆時針移動2格，和順時針移動10格，得到的結果均是一樣的。以算術公式表示則是4-2和4+10，一眼看出4-2明顯不等于4+10，那為什么時鐘上兩者結果卻是相同的呢？

      那是“模”在作怪。當運算結果超出計數范圍時，則會執行求模運算，4+10=14>12，12求模后得到2=4+(-2)。這時你會發現負數的補數必定是正數，那么就解決了需要以正數表示負數的需求。接下來就要驗證以補數解決以正數表示負數后，參與加法運算是否有問題了。

      在深入之前，請大家先了解一下理論：

      補數/補碼/二補碼，若A、B除以M為模執行求模運算后的結果相等，則A與B互為補數，公式：a≡b(mod m)。

      求模公式：mod = a - m * La/mJ，其中LJ代表“取下界”符號。（注意：%是取余而不是取模數的運算符，而求模和取余在本質上是不同的）

         以下以JS來描述

/**
 * @description 求模
 * @method mod
 * @public
 * @param {Number} o - 操作數
 * @param {Number} m - 模，取值范圍：除零外的數字(整數、小數、正數和負數)
 * @returns {Number} - 取模結果的符號與模的符號保持一致
 */
var mod = (o/*perand*/, m/*odulus*/) => {
    if (0 == m) throw TypeError('argument modulus must not be zero!')
    return o - m * Math.floor(o/m)
}

/**
 * @description 求余
 * @method rem
 * @public
 * @param {Number} dividend - 除數
 * @param {Number} divisor - 被除數，取值范圍：除零外的數字(整數、小數、正數和負數)
 * @returns {Number} remainder - 余數，符號與除數的符號保持一致
 */
var rem = (dividend, divisor) => {
    if (0 == divisor) throw TypeError('argument divisor must not be zero!')
    return dividend - divisor * Math.trunc(dividend/divisor)    
}

      補數定理：

　　　　1. 反身性：a≡a(mod m)

　　　　2. 對稱性：若a≡b(mod m)。則b≡a(mod m)

　　　　3. 傳遞性：若a≡b(mod m)，b≡c(mod m)。則a≡c(mod m)

　　　　4. 補數式相加：若a≡b(mod m), c≡d(mod m)。則a+c≡b+d(mod m)，a-c≡b-d(mod m)

　　　　5. 補數式相乘：若a≡b(mod m), c≡d(mod m)。則ac≡bd(mod m)

　　　　6. 互為補數的絕對值相加等于模數：若a≡b(mod m)，則m = |a| + |b|

               示例1：對于有符號數-3(采用補碼編碼：1101)，模m為8（由于最左一位是符號位，不列入模中），對-3取補得到-5(采用補碼編碼：1011)。

　　　　　　　　  得到8=|-3| + |-5|。

　　　　7. 若a、b均為正數，則mod(a + b, m) = mod(a, m) + mod(b, m)

  Derivation

　　有了上述模數的理論后我們可以挽起衣袖開始推導了！

　　首先假設現在以n位二進制位來存儲數據，其中最左一位為符號位，那么模則是2n-1。然后以a表示某正整數，b表示某負整數，并且c為b的補數。

      1. 整理出 b≡c(mod 2n-1)，a≡(mod 2n-1)

　　2. 根據補數式相加得到 a+b≡a+c(mod 2n-1)

　　3. 即 mod(a+b, 2n-1) = mod(a+c, 2n-1)

     4. 回顧模的定義“模，是指一個計量系統的計數范圍，而模則是產生“溢出”的量”，可知當運算過程中產生“溢出”操作，實質上就是執行取模運算。而我們的存儲空間是固定為n位二進制位，因此運算的最后一步默認就是取模運算。因此a+b與a+c在存儲空間固定的前提下，最終結果必然相等。

     上面已經證明了以補數來實現減法加法化，以正數表示負數的有效性。那下面我們來看看將原碼轉換為補碼的規則為什么是成立的。

     假設以n位二進制位來存儲數據，其中最左一位為符號位

　　　　模 = 2n-1 = 1 + 1*2 + 1*22 + ...... + 1*2n-2 + 1

　　　　某負數原碼a = k0 + k1*2 + k2*22 + ...... + kn-2*2n-2

　　根據“互為補數的絕對值相加等于模數：若a≡b(mod m)，則m = |a| + |b|”

　　　  a的補碼 = 2n-1 - a = (1-k0) + (1-k1)*2 + (1-k2)*22 + ...... + (1-kn-2)*2n-2 + 1

      由于k0,k1等的值不是0就是1，因此等價于作取反操作，然后最后再加1。

 

 

Conclusion　　　　　　　　　　　　　　　　　　　　　　　　　　

  ANSI C標準中并沒有規定必須用補碼來表示有符號整數，但幾乎所有實現都采用補碼的表示方式。而Java則規定采用補碼表示有符號整數。

 

  本文嘗試以相對全面的角度描述原碼、反碼和補碼，若有紕漏請給位指正。

  尊重原創，轉載請注明來自：肥子John^_^http://www.cnblogs.com/fsjohnhuang/p/5060242.html

 

Thanks　　　　　　　　　　　　　　　　　　　　　　　　　　　　

http://baike.baidu.com/link?url=aGfE7C12rMLNpPVdMZcKlS9JkQnMRe9iiiUUTnQzLSO8PkKE5dbPtf_dtTUwDORVIehhAJ6jr4BK6v0JfyW9l_#4

http://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html


文章列表



Avast logo

Avast 防毒軟體已檢查此封電子郵件的病毒。
www.avast.com


arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大師兄 的頭像
    大師兄

    IT工程師數位筆記本

    大師兄 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄