一、课上练习

编程练习

1. 输出二进制反码：L2121
2. 字符串的反码：L2122

二、知识总结

✨ 计算机编码的核心思想

编码是信息处理中的基本操作：

• 广义：把信息从一种格式转换为另外一种格式
• 狭义：把信息用二进制数表示
• 作用：方便存储、传输、解析

编码的主要分类：

• 数字编码：用二进制表示数字（原码、反码、补码）
• 字符编码：用二进制表示字符（ASCII、Unicode）
• 多媒体编码：用二进制表示图像、音频、视频
• 压缩编码：减小数据体积的编码方式

✨ 数字编码

计算机内部使用原码、反码和补码三种方式来表示数字。正数的三种编码完全相同，区别在于负数的表示方式。

原码

原码是最直观的二进制表示方式：

• 正数的原码就是其二进制表示
• 负数的原码是在正数的原码基础上将最高位变成 1

以 8 位原码为例：

反码

反码的规则如下：

• 正数的反码就是其二进制表示（与原码相同）
• 负数的反码是将其对应正数的二进制每一位都取反

以 8 位反码为例：

补码

补码是计算机中最常用的数字编码方式：

• 正数的补码就是其二进制表示（与原码相同）
• 负数的补码是其反码加 1

以 8 位补码为例：

三种数字编码总结

记忆口诀：

• 正数三码均相同
• 原码负数最左边（最高位置 1）
• 反码正负恰相反（逐位取反）
• 补码负数反加一（反码 + 1）

以 8 位编码为例，完整对比如下：

✨ 位运算

位运算是对二进制数中的位进行操作的方式，是计算机内部高效的运算方式。可以与赋值运算符结合成为位运算赋值运算符。

✨ 字符编码

字符编码用于将字符映射为数字，常见的字符编码标准包括：

ASCII 常用编码值：

记忆技巧：0 < A < a，即数字 < 大写字母 < 小写字母。大写字母和对应小写字母之间相差 32（例如 A(65) 和 a(97)）。

✨ 多媒体编码

编码格式

编码标准

✨ 压缩编码

压缩编码通过特定算法减小数据体积，便于存储和传输：

✨ 计算机编码的执行示例

求 -13 的原码、反码、补码（8位）

第1步：求原码

• 先写出 13 的二进制：13 = 8 + 4 + 1 = 00001101
• -13 的原码：最高位改为 1 → 10001101

第2步：求反码

• 将 13 的二进制每一位取反：00001101 → 11110010

第3步：求补码

• 反码加 1：11110010 + 1 = 11110011

完整对比表：

位运算执行过程：以 5 & 6、5 | 6、5 ^ 6 为例

先将 5 和 6 转为二进制：

• 5 = 101
• 6 = 110

按位与（&）：两位都为 1 才为 1

101   (5)
& 110   (6)
-----
100   (4)

按位或（|）：至少一位为 1 就为 1

101   (5)
| 110   (6)
-----
111   (7)

按位异或（^）：两位不同才为 1

101   (5)
^ 110   (6)
-----
011   (3)

左移右移执行过程

• 5 << 1：将 101 左移 1 位 → 1010 = 10（相当于乘以 2）
• 5 >> 1：将 101 右移 1 位 → 10 = 2（相当于除以 2，向下取整）
• 5 << 2：将 101 左移 2 位 → 10100 = 20（相当于乘以 4）

规律： 左移 k 位相当于乘以 2^k，右移 k 位相当于除以 2^k（向下取整）。

✨ 计算机编码的解题步骤

例题：求 -20 的 8 位补码

解题步骤：

1. 求 20 的二进制：20 = 16 + 4 = 00010100
2. 求反码（每位取反）：00010100 → 11101011
3. 反码加 1 得补码：11101011 + 1 = 11101100

验证方法： 用补码还原回十进制

• 补码 11101100，最高位是 1，说明是负数
• 取反：00010011，加 1：00010100 = 20
• 所以原数是 -20

例题：用位运算判断一个整数是奇数还是偶数

if (n & 1) {
    cout << "奇数" << endl;
} else {
    cout << "偶数" << endl;
}

原理： 任何整数的二进制最低位为 1 则是奇数，为 0 则是偶数。n & 1 取出最低位进行判断，比 n % 2 更高效。

✨ 计算机编码的常见错误

1. 原码和反码混淆：原码是"最高位变1"，反码是"每一位取反"。例如 -5 的原码是 10000101（只改最高位），反码是 11111010（全部取反），两者完全不同
2. 补码计算时忘记进位：反码加 1 时可能产生进位，例如反码 11111111 + 1 = 100000000，8 位补码只保留低 8 位为 00000000
3. 正数的三码不同：正数的原码、反码、补码完全相同，只有负数才需要转换
4. 位运算优先级陷阱：在 C++ 中，&、|、^ 的优先级低于比较运算符。if (a & 1 == 1) 实际上是 if (a & (1 == 1))，应该写成 if ((a & 1) == 1)
5. 左移溢出：左移位数过多可能导致数据溢出，例如 1 << 31 在 int 类型中会变成负数

✨ 格雷码

概念

格雷码（Gray Code）是由贝尔实验室的弗兰克·格雷在 1947 年发明的，又称反射二进制码，是一种特殊的二进制编码系统。

格雷码的特点：

• 单步变化性：两个连续的数值编码仅有一位二进制数不同
• 循环性：最大值和最小值之间编码也仅有一位二进制数不同

主要应用：数字系统错误检测、模拟数字转换、位置编码。

格雷码构造方法

手动构造法

k 位格雷码，从全 0 开始交替执行以下两步：

1. 翻转最低位得到下一个格雷码
2. 翻转最右边的 1 的左边一位得到下一个格雷码

重复操作 1 和 2 共 2^k - 1 次后，完成编码。

镜像构造法

从 1 位格雷码 0、1 开始，逐步扩展：

1. 将 k-1 位格雷码上下镜像复制
2. 前 k 个格雷码左边补 0
3. 后 k 个格雷码左边补 1

重复 k-1 次补位操作后完成编码。

镜像构造过程示例：

格雷码与二进制编码之间的转换

二进制码转格雷码

工作原理：

1. 保留二进制的最高位作为格雷码的最高位
2. 对于二进制数后面的每一位：该位与它左边的一位异或得到格雷码的下一位

g(n) = n ^ (n >> 1);

格雷码转二进制码

工作原理：

1. 保留格雷码的最高位作为二进制码的最高位
2. 对于格雷码后面的每一位：将该位与二进制码左边的一位异或得到二进制码这一位

bin[0] = gray[0];
for (int i = 1; i < k; ++i) {
    bin[i] = bin[i - 1] ^ gray[i];
 }

三、课后练习

编程练习

1. 2进制中的0和1：L2123
2. 二进制折半交换：L2124

基础知识练习

• 计算机编码与格雷码 - 选择题