01-数制与整数表示

在计组中，我们主要用四种进位制：二进制、八进制、十进制、十六进制。每一位都有一个位权，等于“基数的某次幂”。例如：

考试中最常见的转换：

• 二进制 ↔ 八进制：每 3 位二进制一组；
• 二进制 ↔ 十六进制：每 4 位二进制一组；
• 二进制 ↔ 十进制：用位权展开，或者除基取余 / 乘基取整法。

对一个 n 位有符号整数，常见有三种表示方式：

1. 原码（sign-magnitude）
   • 最高位是符号位：0 表示正，1 表示负；
   • 其余 n-1 位表示数值的绝对值；
   • 取值范围：- (2^{n-1} - 1) \sim + (2^{n-1} - 1)，存在 +0 和 -0 两种 0。
2. 反码（ones’ complement）
   • 正数：与原码相同；
   • 负数：对相应正数的各位取反；
   • 范围也为 - (2^{n-1} - 1) \sim + (2^{n-1} - 1)，同样有 +0 和 -0。
3. 补码（two’s complement）
   • 正数：与无符号数表示相同；
   • 负数：先取反码再加 1，同时负数-x的补码是2^n - x；
   • 如 110110110_2 = 182，所以表示的真实的数字应该是=-2^n+x = 182-256=-74
   • 范围：-2^{n-1} \sim + (2^{n-1} - 1)，只有 一个 0；
   • 现代计算机和考研题中主要使用补码。

为什么大家都用补码？

• 加法器“一统天下”：减法直接加补码，硬件更简单；
• 只有一个零（+0 和 -0 不再重复）；
• 溢出检测简单（上面两条快规就是硬件判定逻辑的本质）。
  对 8 位补码：范围 [−128,+127]。
• 10000000₂ = 128-256 = -128（最小值）；01111111₂ = +127（最大值）。

常用编码：BCD、Gray、奇偶校验

1. BCD 码（8421 码为主）

8421 BCD：

• 用 4 位二进制表示 1 个十进制数字（0~9）。
  • 0000 = 0, 0001 = 1, …, 1001 = 9
  • 1010~1111：无效状态
    用途：
• 便于十进制显示、金融/商业计算等（十进制精确表示）。

一、Gray 码（格雷码）

1. Gray 码到底是啥？（概念与特点）

定义（直观理解）：
Gray 码是一种相邻两个码字只有 1 位不同的编码。

• 若把 0,1,2,3,… 按顺序编码成一列二进制串，
  用普通二进制：相邻数可能会好几位一起变化
  用 Gray 码：相邻两个数之间只改变 1 个比特。
  核心特点：

1. 相邻码字汉明距离 = 1（就这一点超级重要）
2. 常用于：
   • 旋转编码器、位置检测
   • A/D 转换器、机械电气交界处
     因为“只变一位” ⇒ 读数时不容易因为多个位同时抖动而产生错数。

小结一句：
Gray 码 = “按顺序走，每次只翻动一个开关”的二进制编码。

二进制转格雷码：
n 位二进制数 b_{n-1}b_{n-2}...b_0，n 位格雷码 g_{n-1}g_{n-2}...g_0
则，g_{n-1}=b_{n-1},g_{i}=b_{i} \text{xor} b_{i+1}

用“位运算口语版”记：

• Gray 最高位 = 二进制最高位
• Gray 的其它每一位 = 二进制相邻两位异或

格雷码转二进制：
b_{n-1}=g_{n-1},b_i = b_{i+1} \text{xor} g_i 从高往低算

口语版记忆：

• 二进制最高位 = Gray 最高位
• 后面的每一位：“上一位二进制” XOR “这一位 Gray”

奇偶校验

基本概念：用 1 位检查“有没有（可能）错”

假设一个数据字是若干位二进制：d_{n−1}d_{n−2}\dots d_1d_0

奇偶校验 = 在数据上再加 1 位校验位 p，用来检测传输过程中是否出现错误（特别是单比特错误）。

• 加完后整体为：pd_{n−1}d_{n−2}\dots d_1d_0
  整个字（含校验位）中 1 的个数为奇数/偶数。

能做：

• 能检测出全部的 单比特错误：
  • 因为如果只有 1 位翻转，1 的个数一定改变“奇偶性”。

不能做：

• 不能确定位出错的具体位置
  ⇒ 只能“报错”，不能“纠错”。
• 对 偶数个比特同时翻转，可能检测不到：

移码（Biased Code）

• 定义：移码 = 真值 + 偏置量（Bias），常取 Bias = 2^{n-1}
• 对 n 位移码，有：
  \text{移码} = \text{补码} \oplus 100\cdots0
  （即“补码”最高位取反）
  特点：
• 所有真值按大小排列，对应的移码也按无符号大小递增
• 典型用途：浮点数指数部分，比较大小方便。

定点小数

• 常见约定：小数点在“符号位”之后：
  (\text{符号位}.\text{小数位}\ \text{小数位}\cdots)_2
• 例如：对于 n 位补码定点小数（1 位符号 + n-1 位小数），真值范围为：
  -1 \le X \le 1 - 2^{-(n-1)}

溢出判断的关键结论

对补码加法 S=A+B

只有“同号相加”才可能溢出：

• 正 + 正 → 得到负数：正溢出（超上界）
• 负 + 负 → 得到正数：负溢出（超下界）

符号位判定法：若 A_s = B_s​ 且 S_s \ne A_s，则发生溢出。

注意：最高位进位 ≠ 必然溢出，进位被丢弃不代表错，是否溢出要看符号位变化。