数制、编码与整数的表示

本节导读

「数据的表示和运算」是组成原理里计算最密集的一章，本课分两节讲：这一节讲数制与编码、整数的表示（2022 年版的「真值和机器数」「字符与字符串」也在这里），下一节讲运算方法、运算电路和浮点数。

这一节的题目几乎都要动手算：进制转换、求各种机器码、判断表示范围、读懂 C 程序里类型转换之后的值。学完你应该能在 8 位、16 位、32 位之间熟练地做补码转换和扩展、截断。

进位计数制

r 进制数的每一位乘上它的位权 $r^{i}$ri 再相加，就得到十进制值。常用转换：

转换	方法
二进制 ↔ 八进制、十六进制	以小数点为界，向左、向右每 3 位（或 4 位）一组，不足补 0
十进制整数 → 二进制	除 2 取余，先得到的是低位
十进制小数 → 二进制	乘 2 取整，先得到的是高位；有的小数（如 0.1）乘不尽，只能近似
二进制 → 十进制	按位权展开相加

例如 $0.6875 \times 2 = 1.375$0.6875×2=1.375 取 1，$0.375 \times 2 = 0.75$0.375×2=0.75 取 0，$0.75 \times 2 = 1.5$0.75×2=1.5 取 1，$0.5 \times 2 = 1.0$0.5×2=1.0 取 1，所以 $0.6875 = (0.1011)_2$0.6875=(0.1011)2​。8421 BCD 码用 4 位二进制表示一位十进制数，例如 59 写成 0101 1001。

真值、机器数与定点数的编码

带正负号的数叫真值，把符号也数码化（0 正 1 负）后的数叫机器数。设机器数共 n + 1 位（1 位符号、n 位数值）：

编码	求法（负数）	0 的表示	定点整数的范围
原码	符号位为 1，数值位为绝对值	有 +0、−0 两种	$-(2^{n}-1) \sim 2^{n}-1$−(2n−1)∼2n−1
反码	原码的数值位逐位取反	有两种	$-(2^{n}-1) \sim 2^{n}-1$−(2n−1)∼2n−1
补码	反码末位加 1，即 $2^{n+1} + x$2n+1+x	唯一	$-2^{n} \sim 2^{n}-1$−2n∼2n−1
移码	真值加偏置 $2^{n}$2n，即补码的符号位取反	唯一	$-2^{n} \sim 2^{n}-1$−2n∼2n−1

正数的原码、反码、补码相同。补码的好处是减法可以变成加法、0 只有一种表示，所以计算机里带符号整数都用补码。已知 $[x]_{\text{补}}$[x]补​ 求 $[-x]_{\text{补}}$[−x]补​：连同符号位一起取反，末位加 1。移码保持了大小顺序，便于比较，浮点数的阶码就用它。定点小数的补码范围是 $-1 \sim 1 - 2^{-n}$−1∼1−2−n。

无符号整数与带符号整数

n 位无符号整数表示 $0 \sim 2^{n}-1$0∼2n−1，n 位带符号整数（补码）表示 $-2^{n-1} \sim 2^{n-1}-1$−2n−1∼2n−1−1。同一个位串按两种方式解释，值可能不同：最高位为 0 时相同；最高位为 1 时，无符号值比带符号值大 $2^{n}$2n。比如 16 位的 1111 1111 1111 1111 当无符号数是 65535，当 short 是 −1。

C 语言的类型转换

C 语言里 char、short、int、long long 一般是 8、16、32、64 位，带符号的用补码。转换规则可以归成三条：

转换	规则	结果
同长度，带符号 ↔ 无符号	位串不变，只换解释方式	负数变成大的无符号数，反之亦然
短 → 长	无符号数零扩展，带符号数符号扩展	数值不变
长 → 短	截断，只保留低位	超出范围时数值改变

另外，带符号数与无符号数一起运算或比较时，带符号数先被转换成无符号数，负数会变成很大的正数，这是 C 程序里常见的隐患。