二进制补码

前言

N 年前接触二进制编码的时候，对补码一知半解，不是很懂，直到看了 CS:APP （深入理解计算机系统）中相关章节，才恍然大悟，真正理解。

无符号数的编码

无符号数的二进制编码比较简单直观。假设一个整数数据类型有 $w$ 位，将位向量 $\vec{x}$ 写作 $[x_{w-1},x_{w-2},\ldots,x_0]$ ，用函数 $B2U_w$ (Binary to Unsigned)来表示：

$$B2U_w(\vec{x})=\sum_{i=0}^{w-1} x_i 2^i$$

函数$B2U_w$将一个长度位$w$位的 $0$、$1$ 串映射到非负整数。举个栗子：

$$B2U_4([0001])=0\cdot 2^3 + 0\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0 = 0+0+0+1=\ 1$$
$$B2U_4([0101])=0\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0 = 0+4+0+1=\ 5$$
$$B2U_4([1011])=1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 8+0+2+1=11$$
$$B2U_4([1111])=1\cdot 2^3 + 1\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 = 8+4+2+1=15$$

$w$位所能表示的值的范围，最小值用位向量$[00\cdots 0]$表示，也就是整数值$0$，而最大值用位向量$[11\cdots 1]$表示，即整数值$UMax_w=\sum_{i=0}^{w-1} 2^i = 2^w-1$。

无符号数的二进制表示有一个很重要的属性，就是每个介于$0\sim 2^w -1$之间的数都有唯一一个$w$位的值编码。

补码编码

最常见的有符号数的计算机表示方式就是补码（two’s complement）形式。在这个定义中，将字的最高有效位解释为负权（negative weight）。用函数$B2T_w$(Binary to Two’s complement)来表示：

$$B2T_w(\vec{x})=-x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i$$

最高有效位$x_{w-1}$也称为“符号位”，它的权重为$-2^{w-1}$，而在无符号数中，它的绝对值代表权重。符号位设置为$1$时，表示值为负，而当设置为$0$时，表示非负数。

$$B2T_4([0001])= -0 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = \ 0+0+0+1=\ 1$$
$$B2T_4([0101])= -0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = \ 0+4+0+1=\ 5$$
$$B2T_4([1011])= -1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = - 8+0+2+1= -5$$
$$B2T_4([1111])= -1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = - 8+4+2+1= -1$$

$w$位所能表示的值的范围，最小值是$[10\cdots 0]$，即整数值$TMin_w=-2^{w-1}$；最大值是$[01\cdots 1]$，其整数值为$TMax_w=\sum_{i=0}^{w-2}=2^{w-1}-1$。

一些性质

$$|TMin|=|TMax|+1$$
$$UMax=2TMax+1$$