補數
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
補數(complement)是對於給定的進位制,相加後能使自然數 a 的位數增加 1 的最小的數。可以在計算電路中,代替減的操作,而僅僅使用加法元器件(加法器)的「加上的補數(無視最高位的進位)」,達到相同的效果。
定義
設b 進位表示自然數 a 至少需要 n 位數字,規定
- 是 「b 進位數 a 的關於基數的補數(b 的補數)」
- 是「b 進位數 a 的關於減基數的補數(b - 1 的補數,簡稱減補數、儕補數)」。
例如,十進位自然數 61 關於基數 10 的補數是 。二進位自然數 關於基數 2 的補數是 。
由定義可以得出,a 的基數的補數 加上 a,可以得到位數多一位的最小的自然數()。a 的減基數的補數 加上 a ,可以得到位數不增加的最大的自然數()。
基數 b 在上下文中明確的時候,「在b 進位中」的描述通常被省略。
但是,在基數不明確的情況下,「 的補數」表示的可以是 進位的減基數的補數,也可是 進位的基數的補數,從而產生歧義(這兩者的值不一定是相等的)。例如,僅僅說「9的補數」,無法確定指的是「10進位中的減基數的補數」還是「9進位中的基數的補數」。
在英文中,十進位的基數的補數記為 ten's complement,減基數的補數稱為 nines' complement。二進位中,基數的補數稱為 two's complement,減基數的補數稱為 ones' complement。其他進位也有類似的稱法。一些人,如高德納,建議採用撇號區分。這樣,four's complement指的是四進位中的基數的補數。而fours' complement指的是五進位中的減基數的補數。但是,這並不是普遍的做法,而且在幾乎所有情況下進位是明確的。多數作者寫做 one's和nine's complement,一些格式手冊建議採用 ones和nines complement,不採用撇號。
計算方法
對於N進位的自然數a,從個位開始的各位數字
規定不能為0。規定的各位為:
- bi = (N + 1) + ai
這時,N進位形如的
數 即稱為「 的關於 的補數」。
10進位的舉例
求十進位數 2304671 的補數。由於 9 = 2 + 7 = 3 + 6 = 0 + 9 = 4 + 5 = 6 + 3 = 7 + 2 = 1 + 8 ,令N=9時,自然數2304671對應的補數為 7695328 。 7695328 + 1 = 7695329 ,因此N=10時,自然數2304671對應的補數是 7695329。
2進位的舉例
二進位中有 1 + 1 = 0, 1 + 0 = 1,求1的補數只需簡單地將0與1相互替換。(位元運算中的邏輯非運算)。
求二補數(即二補數),只需要將1的補數加1。
- 二進位的 101010110 對應的1的補數是 010101001。
- 2 的補數是 010101001 + 1 = 010101010。
參考文獻
JIS X 0005:2002 情報処理用語(データの表現) 05.08
Donald E. Knuth 『The Art of Computer Programming Vol. 2 Seminumerical Algorithms Third Ed. 日本語版』 アスキー、2004年、191頁。 (ISBN 4-7561-4543-4)