第一章进制与编码

学习目标

理解进制（Binary, Octal, Hexadecimal）的基本概念，掌握不同进制之间的转换方法
掌握二进制算术运算和逻辑运算的基本规则
理解计算机中整数的表示方式：原码、反码和补码
理解浮点数的IEEE 754编码标准
了解字符编码的发展历程，掌握ASCII码和UTF-8编码的基本原理
理解布尔代数的基本运算和门电路基础

1.1 进制的概念

1.1.1 什么是进制

进制（Numeral System）是一种记数的方法，也称为进位计数法。在日常生活中，我们最熟悉的是十进制（Decimal），它使用0到9这十个数字来表示数值。为什么是十进制呢？有一种说法是人类天生有十根手指，当古人开始数数时，很自然地会用手指来辅助计数，十根手指用完后就需要"进位"，于是就产生了十进制。

然而，在计算机科学中，二进制（Binary）是最重要的进制。计算机是由复杂的电子电路构成的，而电路只有两种基本状态：通电和断电。我们用"1"表示通电状态，用"0"表示断电状态，这就是计算机使用二进制的原因。每一个二进制位（bit）就是一次电路状态的选择。

除了二进制之外，八进制（Octal）和十六进制（Hexadecimal）也是计算机领域常用的进制。八进制使用0到7这八个数字，十六进制则使用0到9以及字母A到F（代表10到15）共16个符号。选择十六进制的原因是它与二进制之间的转换非常方便——每4个二进制位恰好对应1个十六进制位。

1.1.2 进制的表示方法

当我们写一个数字时，不同进制会用不同的下标来区分。例如：

$1011_2$ 表示二进制数 1011
$273_8$ 表示八进制数 273
$159_{10}$ 或简单的 159 表示十进制数 159
$3FA_{16}$ 表示十六进制数 3FA

在计算机编程中，为了明确区分不同的进制，通常会有特殊的表示方法。以C语言为例：

二进制数通常以 0b 或 0B 开头，例如 0b1011
八进制数以 0 开头，例如 0273
十六进制数以 0x 或 0X 开头，例如 0x3FA

1.1.3 进制的权值

理解进制的关键是权值（Weight）的概念。在十进制中，每个位上的数字都有不同的权值，从右到左依次是个位、十位、百位、千位……也就是说，每向左移动一位，权值就扩大10倍。个位的权值是 $10^0 = 1$，十位的权值是 $10^1 = 10$，百位的权值是 $10^2 = 100$，以此类推。

类似地，在二进制中，每一位的权值是2的幂次方，从右到左依次是 $2^0, 2^1, 2^2, 2^3, \ldots$。因此，二进制数 $1011_2$ 转换为十进制就是：

\[1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = 11\]

在八进制中，每一位的权值是8的幂次方。所以八进制数 $273_8$ 转换为十进制是：

\[2 \times 8^2 + 7 \times 8^1 + 3 \times 8^0 = 2 \times 64 + 7 \times 8 + 3 \times 1 = 128 + 56 + 3 = 187\]

十六进制的权值是16的幂次方。十六进制数 $3FA_{16}$ 转换为十进制是：

\[3 \times 16^2 + 15 \times 16^1 + 10 \times 16^0 = 3 \times 256 + 15 \times 16 + 10 \times 1 = 768 + 240 + 10 = 1018\]

1.1.4 二进制的特点

二进制在计算机中的广泛应用不是偶然的，而是由其物理特性决定的：

简单性：二进制只需要表示两种状态，这使得电路设计大大简化。在实际电路中，"通电"和"断电"很容易实现和区分，而要电路表示十种状态就非常困难了。

可靠性：两种状态之间的区分非常清晰，不容易受到干扰。即使有轻微的电压波动，也能可靠地区分"高电平"和"低电平"。

运算简单：二进制的运算规则比十进制简单得多。加法规则只有四条：0+0=0，0+1=1，1+0=1，1+1=10（进位）。乘法规则也只有四条：0×0=0，0×1=0，1×0=0，1×1=1。

逻辑基础：二进制与布尔代数（Boolean Algebra）完美契合，可以方便地实现各种逻辑运算，为计算机的逻辑判断能力奠定了基础。

本节小结

进制是进位计数法，二进制是计算机的基础，因为它只有两种状态
八进制和十六进制在计算机中也常用，它们与二进制转换方便
每一位的权值等于基数的幂次方，从右到左依次增大

1.2 进制转换

1.2.1 十进制转换为其他进制

将十进制数转换为其他进制，除基取余法是最常用的方法。具体步骤是：用目标进制的基数连续去除十进制数，每次取余数，直到商为0，然后将所有余数逆序排列。

十进制转二进制：将十进制数除以2，记录余数，直到商为0。

例如，将十进制数13转换为二进制：

\[13 \div 2 = 6 \cdots\cdots 1 \quad \text{（余数1）}$$ $$6 \div 2 = 3 \cdots\cdots 0 \quad \text{（余数0）}$$ $$3 \div 2 = 1 \cdots\cdots 1 \quad \text{（余数1）}$$ $$1 \div 2 = 0 \cdots\cdots 1 \quad \text{（余数1）}\]

将余数逆序排列，得到 $1101_2$。验证：$1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13$，正确。

十进制转十六进制：将十进制数除以16，记录余数。

例如，将十进制数423转换为十六进制：

\[423 \div 16 = 26 \cdots\cdots 7 \quad \text{（余数7）}$$ $$26 \div 16 = 1 \cdots\cdots 10 \quad \text{（余数A）}$$ $$1 \div 16 = 0 \cdots\cdots 1 \quad \text{（余数1）}\]

逆序排列得到 $1A7_{16}$。

1.2.2 其他进制转换为十进制

将其他进制转换为十进制的方法是按权展开求和法。将每一位数字乘以该位的权值，然后求和。

二进制转十进制：将二进制数的每一位乘以对应的2的幂次方，然后求和。

例如，$101101_2$ 转换为十进制：

位位置	5	4	3	2	1	0
位值	1	0	1	1	0	1
权值	$2^5$	$2^4$	$2^3$	$2^2$	$2^1$	$2^0$
贡献	32	0	8	4	0	1

总和：$32 + 0 + 8 + 4 + 0 + 1 = 45$

十六进制转十进制：将十六进制数的每一位乘以16的幂次方。

例如，$2AF_{16}$ 转换为十进制：

\[2 \times 16^2 + 10 \times 16^1 + 15 \times 16^0 = 2 \times 256 + 10 \times 16 + 15 \times 1 = 512 + 160 + 15 = 687\]

1.2.3 二进制与八进制、十六进制的转换

由于8和16都是2的幂次方，二进制与八进制、十六进制之间的转换非常容易。

二进制转八进制：将二进制数从右到左每3位分成一组（不足三位时在左边补0），然后将每组转换为对应的八进制数。

例如，$1101011_2$ 转换为八进制：

分组：110 | 101 | 1（补0后为001）

110 → 6
101 → 5
001 → 1

结果：$155_8$

八进制转二进制：将每位八进制数转换为3位二进制数。

例如，$72_8$ 转换为二进制：

7 → 111
2 → 010

结果：$111010_2$

二进制转十六进制：将二进制数从右到左每4位分成一组（不足四位时在左边补0），然后将每组转换为对应的十六进制数。

例如，$110101101_2$ 转换为十六进制：

分组：1 | 1010 | 1101（注意第一组补0变成0001）

0001 → 1
1010 → A
1101 → D

结果：$1AD_{16}$

十六进制转二进制：将每位十六进制数转换为4位二进制数。

例如，$3B_{16}$ 转换为二进制：

3 → 0011
B(11) → 1011

结果：$00111011_2$

1.2.4 常见进制对照表

下面是一些常见的十进制、二进制、八进制、十六进制数值的对照表：

十进制	二进制	八进制	十六进制
0	0	0	0
1	1	1	1
2	10	2	2
3	11	3	3
7	111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
15	1111	17	F
16	10000	20	10
31	11111	37	1F
32	100000	40	20
63	111111	77	3F
64	1000000	100	40
127	1111111	177	7F
128	10000000	200	80
255	11111111	377	FF

1.2.5 小数部分的转换

带小数的进制转换稍微复杂一些。对于小数部分，转换方法是将小数部分连续乘以目标基数，每次取整数部分作为新的小数部分，直到小数部分为0（或达到精度要求）。

十进制小数转二进制：将小数部分乘以2，取整数部分，然后继续处理小数部分。

例如，将十进制小数 $0.625$ 转换为二进制：

\[0.625 \times 2 = 1.25 \quad \text{（整数部分1）}$$ $$0.25 \times 2 = 0.5 \quad \text{（整数部分0）}$$ $$0.5 \times 2 = 1.0 \quad \text{（整数部分1）}\]

得到 $0.101_2$。

如果十进制小数无法用二进制精确表示（如0.1），则需要按精度要求截断。例如，$0.1$ 转换为二进制是无限循环的：$0.0001100110011..._2$

本节小结

十进制转其他进制使用"除基取余法"，商为0时逆序取余数
其他进制转十进制使用"按权展开求和法"
二进制与八进制转换：每3位二进制对应1位八进制
二进制与十六进制转换：每4位二进制对应1位十六进制
小数部分转换使用"乘基取整法"

1.3 二进制运算

1.3.1 二进制加法

二进制加法是计算机最基本的运算之一，它遵循以下四条规则：

$0 + 0 = 0$，进位为0
$0 + 1 = 1$，进位为0
$1 + 0 = 1$，进位为0
$1 + 1 = 10$，进位为1

这与十进制加法类似，只不过当结果大于等于2时就要进位。在十进制中，$9 + 9 = 18$ 产生进位1；在二进制中，$1 + 1 = 10$ 也产生进位1。

竖式计算示例：计算 $1101_2 + 1011_2$

计算过程（从右到左）： - 第0位：$1 + 1 = 10$，写0进1 - 第1位：$0 + 1 + 1$(进位) $= 10$，写0进1 - 第2位：$1 + 0 + 1$(进位) $= 10$，写0进1 - 第3位：$1 + 1 + 1$(进位) $= 11$，写1进1 - 第4位：进位1，写1

结果：$11000_2$（等于十进制24）

1.3.2 二进制减法

二进制减法可以看作是加法的逆运算，但计算机通常不直接做减法，而是通过补码运算来实现。为了完整性，我们先介绍直接的减法运算规则：

$0 - 0 = 0$，借位为0
$1 - 0 = 1$，借位为0
$1 - 1 = 0$，借位为0
$0 - 1 = 1$，借位为1（在二进制中，0减1需要从高位借1）

借位示例：计算 $1100_2 - 0101_2$

计算过程： - 第0位：$0 - 1$，不够，向高位借1，$2 + 0 - 1 = 1$，借位1 - 第1位：原本是0，减去借位1后不够，向高位借1，$2 + 0 - 1 = 1$，借位1 - 第2位：原本是1，减去借位1后是0 - 第3位：1减去0还是1

结果：$0111_2$（等于十进制7）

1.3.3 二进制乘法

二进制乘法的规则也很简单：

$0 \times 0 = 0$
$0 \times 1 = 0$
$1 \times 0 = 0$
$1 \times 1 = 1$

乘法过程实际上是被乘数与乘数各位的与运算，然后错位相加。

竖式计算示例：计算 $1101_2 \times 1011_2$

        1101
      × 1011
      ------
        1101    （1101 × 1）
       1101     （1101 × 1，但左移一位）
      0000      （1101 × 0）
     1101       （1101 × 1，但左移三位）
    --------
     10001111

验证：$1101_2 = 13_{10}$，$1011_2 = 11_{10}$，$13 \times 11 = 143_{10}$，$10001111_2 = 143_{10}$，正确。

1.3.4 二进制除法

二进制除法与十进制除法类似，是乘法的逆运算。我们通过一个例子来说明：

计算 $10011_2 \div 11_2$（即 $19_{10} \div 3_{10}$）

结果：商为 $111_2$（7），余数为0。

1.3.5 位运算

位运算（Bitwise Operations）是对二进制数的每一位分别进行操作的运算，这是计算机中非常重要的一类运算。

按位与（AND，&）：对应位都为1时结果为1，否则为0。

例如，$1101_2 \& 1011_2$：

1101
& 1011
------
1001

按位或（OR，|）：对应位只要有一个为1结果就为1，否则为0。

例如，$1101_2 | 1011_2$：

1101
| 1011
------
1111

按位异或（XOR，^）：对应位相异时结果为1，相同则为0。

例如，$1101_2 ^ 1011_2$：

1101
^ 1011
------
0110

按位取反（NOT，~）：将每一位由0变1，由1变0。

例如，$\sim 1101_2 = 0010_2$

1.3.6 移位运算

移位运算包括左移和右移，是二进制运算中非常高效的操作。

左移（<<）：将二进制数的所有位向左移动指定位数，低位补0，高位丢弃。

例如，$0001_2 << 2 = 0100_2$（即 $1 \times 4 = 4$）。左移n位相当于乘以 $2^n$。

右移（>>）：将二进制数的所有位向右移动指定位数，高位补0（或符号位），低位丢弃。

例如，$0100_2 >> 2 = 0001_2$（即 $4 \div 4 = 1$）。右移n位相当于除以 $2^n$（向下取整）。

本节小结

二进制加法遵循"逢二进一"的规则，减法遵循"借一当二"
二进制乘法的本质是被乘数与乘数各位的与运算，然后错位相加
位运算包括与（&）、或（|）、异或（^）、取反（~）
左移n位相当于乘以 $2^n$，右移n位相当于除以 $2^n$

1.4 数据编码：整数表示

1.4.1 为什么需要原码、反码、补码

在人类的日常计数中，负数通常用"-"符号来表示，比如"-5"。但在计算机中，由于二进制只能表示0和1，我们需要用特殊的方式来表示正数和负数。

原码（Sign-Magnitude）是最简单的表示方法：用一个专门的位（通常是最高位）来表示符号，0表示正数，1表示负数，其余位表示数值的绝对值。例如，8位原码中，+5表示为 00000101，-5表示为 10000101。

原码的优点是直观，人类容易理解。但它有一个致命的问题：0的表示不唯一。在8位原码中，00000000 和 10000000 都表示0，分别代表 +0 和 -0。这种不唯一性会给运算带来麻烦。

更重要的是，原码的加减运算非常复杂。如果用原码计算 1 + (-1)，需要判断符号、比较绝对值、决定是做加法还是减法……这与计算机"简单高效"的设计理念相悖。

补码（Two's Complement）的引入完美解决了这些问题。在补码系统中，0只有一种表示，符号位可以直接参与运算，而且减法可以用加法来实现。因此，现代计算机普遍采用补码来表示有符号整数。

1.4.2 原码

原码的定义很直接：最高位为符号位，0表示正，1表示负，其余位表示数值的绝对值。

以8位二进制为例：

数值	原码表示
+0	00000000
-0	10000000
+1	00000001
-1	10000001
+127	01111111
-127	11111111

原码的优点： - 直观，人类容易理解和阅读 - 符合我们对正负数的直觉认识

原码的缺点： - 0有两种表示，造成资源浪费和逻辑混乱 - 加减运算复杂，需要分别处理符号和绝对值 - 电路实现困难，需要比较绝对值大小来决定是做加法还是减法

1.4.3 反码

反码（One's Complement）是对原码的一种改进。对于正数，反码与原码相同；对于负数，反码是符号位保持不变，数值位按位取反。

例如（8位）： - +5 的反码：00000101（与原码相同） - -5 的反码：11111010（符号位1不变，数值位取反：00000101 → 11111010）

数值	原码	反码
+0	00000000	00000000
-0	10000000	11111111
+1	00000001	00000001
-1	10000001	11111110

反码在一定程度上简化了运算（特别是减法可以通过加反码来实现），但仍然没有解决0有两种表示的问题。

1.4.4 补码

补码（Two's Complement）是目前计算机中普遍采用的有符号数表示方法。补码的定义为：

正数的补码 = 原码
负数的补码 = 反码 + 1（或者说，对原码除符号位外按位取反，然后加1）

例如（8位）： - +5 的补码：00000101 - -5 的补码：11111010 + 1 = 11111011

让我们验证一下：-5 的补码 11111011，加上 +5 的补码 00000101：

  11111011
+ 00000101
---------
 100000000

结果是9位，最高位1溢出丢弃，得到 00000000，结果正确（-5 + 5 = 0）。这说明补码的加法可以直接进行，不需要考虑符号。

补码的关键特性：

0的唯一表示：在8位补码中，00000000 表示0，而10000000 不再表示-0，而是-128。这使得补码能够表示-128到127的整数范围（共256个值），而原码和反码只能表示-127到127（因为有+0和-0）。
符号位参与运算：补码的符号位可以参与正常的加减运算，简化了电路设计。
减法变加法：a - b = a + (-b)，而 -b 的补码可以通过取反加一得到。
模运算性质：补码本质上是模运算。以8位为例，模为256。-1 的补码是255（11111111），所以 1 + (-1) = 1 + 255 = 256 ≡ 0 (mod 256)。

补码的取值范围：

对于n位补码： - 能表示的最大正数：$2^{n-1} - 1$（如8位时为127） - 能表示的最小负数：$-2^{n-1}$（如8位时为-128） - 总共能表示 $2^n$ 个不同的值

1.4.5 补码的直观理解

理解补码有一个很好的比喻：钟表模型。

想象一个12小时的钟表，当前时间是11点，如果要减掉3小时，可以： - 直接往回拨：11 - 3 = 8 - 或者往前拨（因为12 - 3 = 9）：11 + 9 = 20 = 8（超过12的部分溢出丢弃）

在这个例子中，"往前拨"的操作就是"加补数"。如果我们把钟表看作12进制的补码系统，那么-3的补码就是12 - 3 = 9。

对于8位二进制，模是256，-1 的补码就是 256 - 1 = 255（二进制11111111）。这就像在一个模256的循环中，-1 和 255 是"等价"的。

1.4.6 整数溢出

当运算结果超出数据类型的表示范围时，就会发生溢出（Overflow）。

以8位有符号整数为例：

最大值是127（01111111）
最小值是-128（10000000）

如果计算 127 + 1：

  01111111  (+127)
+ 00000001  (+1)
---------
  10000000  (-128！)

结果变成了-128，而不是128。这就是上溢（Overflow）。

如果计算 -128 - 1：

  10000000  (-128)
+ 11111111  (-1的补码)
---------
  01111111  (+127！)

结果变成了+127，这就是下溢（Underflow）。

对于无符号整数，溢出后同样会"回绕"：255 + 1 = 0，0 - 1 = 255。

溢出检测：在计算机体系结构中，溢出标志位（Overflow Flag）用于指示最近一次算术运算是否发生了溢出。

本节小结

原码是最直观的表示法，但0有两种表示，加减运算复杂
反码改进了负数表示，但仍有+0和-0的问题
补码是现代计算机的标准表示法：正数不变，负数是反码加1
补码的优势：0表示唯一，符号位可参与运算，减法变加法
n位补码的范围是 $-2^{n-1}$ 到 $2^{n-1} - 1$
运算结果超出范围会发生溢出

1.5 浮点数编码：IEEE 754

1.5.1 浮点数的由来

整数可以精确表示，但现实世界中还有很多需要表示小数。比如圆的周长是直径的 $\pi$ 倍（$\pi \approx 3.14159...$），或者计算复利时需要的指数运算。这些都不能用整数来精确表达。

定点数（Fixed-Point Number）是最早的小数表示方法。假设我们用8位表示小数，约定前4位是整数部分，后4位是小数部分。那么二进制数 00010010 就表示 $1.010_2 = 1.625_{10}$。

但定点数的问题是范围和精度固定。如果用前4后4的约定，最大值只能是 11111111 = $15.9375_{10}$，最小精度是 $1/16 = 0.0625$。对于科学计算来说，这个范围和精度往往不够用。

浮点数（Floating-Point Number）借鉴了科学计数法（Scientific Notation）的思想。科学计数法中，一个数可以表示为：

\[\pm M \times 10^E\]

其中，M是尾数（Mantissa），E是指数（Exponent）。例如，光速 $299792458 \text{ m/s}$ 可以写成 $2.99792458 \times 10^8$。

类似地，浮点数表示为：

\[\pm M \times 2^E\]

这样既可以表示很大范围的数，也可以表示很小的数。

1.5.2 IEEE 754标准概述

IEEE 754是美国电气电子工程师协会制定的浮点数运算标准，是目前几乎所有现代计算机采用的浮点数表示法。

IEEE 754定义了两种精度的浮点数：

单精度（Single Precision）：32位，也称为float
1位符号位（Sign）
8位指数位（Exponent）
23位尾数位（Fraction/Mantissa）
双精度（Double Precision）：64位，也称为double
1位符号位
11位指数位
52位尾数位

此外还有16位的半精度（用于深度学习等场景）和128位的四精度（用于高精度计算）。

1.5.3 浮点数的结构

IEEE 754浮点数的结构如下：

符号位 S  |  指数部分 E  |  尾数部分 M（隐藏位）
   1位         k位           n位

符号位（S）：0表示正数，1表示负数。注意，符号位与尾数、指数都独立，单独决定正负。

指数部分（E）：用于表示2的幂次方。采用偏移码（Biased Exponent）表示，即指数的真实值 = 指数位表示的值 - 偏移量。对于单精度，偏移量是127；对于双精度，偏移量是1023。

尾数部分（M）：也称为小数部分或有效数字。IEEE 754的尾数部分采用隐藏位（Hidden Bit）技术：对于规格化数，尾数实际上有24位（单精度），但最高位1是隐藏的，不存储在浮点数中。这相当于二进制科学计数法中尾数的整数部分总是1（如 $1.011_2 \times 2^E$），所以这个1不需要存储。

1.5.4 规格化浮点数

规格化（Normalized）浮点数是IEEE 754的"正常"表示形式，其特点是：尾数的最高位（即隐藏位）为1，所以尾数的值在 $[1, 2)$ 范围内。

规格化浮点数的指数部分不能是全0或全1（全0和大全1有特殊含义，见下文）。

以32位单精度为例：

\[(-1)^S \times 1.\text{尾数} \times 2^{(E - 127)}\]

例如，十进制数 $6.5$ 的二进制是 $110.1 = 1.101 \times 2^2$： - 符号位S = 0（正数） - 指数 = 2 + 127 = 129 = 10000001 - 尾数 = 101（后续补0）

所以 $6.5$ 的浮点表示为：0 10000001 10100000000000000000000

验证：$(-1)^0 \times 1.101 \times 2^{(129-127)} = 1.101_2 \times 2^2 = 110.1_2 = 6.5_{10}$

1.5.5 特殊值

IEEE 754定义了一些特殊的浮点值：

1. 零（Zero） 指数部分全0，尾数部分全0。注意，+0和-0是不同的：符号位分别为0和1。

2. 非规格化数（Denormalized Number） 指数部分全0，但尾数部分非0。这些数的指数是固定的 $-126$（单精度），可以表示非常接近0的数，但精度会降低。它们的出现是为了让浮点数能够渐进下溢（Gradual Underflow），而不是突然从最小正数跳到零。

3. 无穷大（Infinity） 指数部分全1，尾数部分全0。符号位决定是正无穷还是负无穷。当除以零或运算结果超出表示范围时，会得到无穷大。

4. NaN（Not a Number） 指数部分全1，尾数部分非0。表示未定义或无法表示的结果，如 $0/0$、$\sqrt{-1}$、$\infty - \infty$ 等。

1.5.6 浮点数的取值范围和精度

以32位单精度为例：

类别	最小值	最大值
规格化正数	$2^{-126} \approx 1.18 \times 10^{-38}$	$(2 - 2^{-23}) \times 2^{127} \approx 3.4 \times 10^{38}$
非规格化正数	$2^{-149} \approx 1.4 \times 10^{-45}$	略小于最小规格化正数

精度：单精度浮点数的尾数有23位，但加上隐藏的1位，实际有24位精度，约等于6到7位十进制数字。双精度有53位精度，约等于15到16位十进制数字。

这意味着： - 浮点数不能精确表示所有小数，很多是近似值 - 浮点数运算不满足结合律：如 $(a + b) - b$ 不一定等于 $a$ - 比较浮点数是否相等要格外小心

1.5.7 浮点数的误差

浮点数的误差是一个重要且容易被忽视的问题。

舍入误差（Rounding Error）：由于尾数位数有限，很多小数无法精确表示，必须舍入到最近的可表示值。例如，十进制0.1在二进制中是无限循环的：$0.000110011001100..._2$，必须截断。

抵消误差（Cancellation Error）：当两个相近的数相减时，有效数字会大大减少。例如，$1.0000001 - 1.0000000 = 0.0000001$，原本有7位有效数字，结果可能只剩下1位。

实例分析：

# Python代码演示浮点数误差
a = 0.1 + 0.2
print(a)  # 输出 0.30000000000000004，而不是精确的 0.3
print(a == 0.3)  # 输出 False

这是因为 0.1、0.2 和 0.3 在二进制浮点数中都无法精确表示。

本节小结

浮点数借鉴了科学计数法的思想，用尾数和指数来表示很大或很小的数
IEEE 754是浮点数表示的国际标准，规定了32位单精度和64位双精度格式
单精度浮点数由1位符号、8位指数、23位尾数组成，采用偏移码和隐藏位技术
指数全0和全1有特殊含义，分别表示非规格化数和特殊值（无穷大、NaN）
浮点数精度有限，存在舍入误差，进行浮点运算时要格外小心

1.6 字符编码

1.6.1 为什么需要字符编码

计算机内部只有0和1，那么文字、符号是如何存储的呢？这就需要字符编码（Character Encoding）——将字符映射为数字，再将数字映射为二进制。

如果字符编码不统一，就会出现乱码问题。例如，一段用UTF-8编码的中文文本，如果用GBK编码来解析，就会显示为乱码。这是因为同一种字符（如"中"字）在不同编码中对应不同的数字。

1.6.2 ASCII码

ASCII（American Standard Code for Information Interchange，美国信息交换标准代码）是最早的字符编码标准，诞生于1963年。

ASCII使用7位（后来扩展为8位）来表示128个字符，包括：

控制字符（0-31和127）：如换行（LF）、回车（CR）、制表符（Tab）等，不可打印
可打印字符（32-126）：包括空格、英文大小写字母（A-Z: 65-90, a-z: 97-122）、数字0-9（48-57）、标点符号等

常用ASCII码对照： - 字符'0'的ASCII码是48，二进制是 00110000 - 字符'A'的ASCII码是65，二进制是 01000001 - 字符'a'的ASCII码是97，二进制是 01100001

ASCII码的特点： - 只用了7位，最高位为0 - 只包含英文字母、数字和少量符号 - 足以支持英文，但无法表示中文等其他语言

1.6.3 扩展编码

由于ASCII只能表示128个字符，对于需要更多字符的语言（如欧洲语言使用的带重音字母）来说不够用。

ISO-8859-1（Latin-1）将ASCII的最高位利用起来，用8位表示256个字符。它覆盖了大多数西欧语言，但仍然无法表示中文、日文等。

GB2312/GBK/GB18030是中国制定的汉字编码标准： - GB2312：1980年发布，收录6763个汉字和682个图形符号 - GBK：GB2312的扩展，收录21003个汉字 - GB18030：最新标准，收录70000多个汉字，还包含了藏文、蒙文等少数民族文字

BIG5是繁体中文编码，主要在台湾、香港、澳门使用。

1.6.4 Unicode与UTF-8

随着互联网的普及，需要一种能够表示世界上所有文字的编码系统。Unicode应运而生。

Unicode的目标是为每一个文字符号分配一个唯一的编码（称为码点，Code Point），无论是什么语言、什么平台。Unicode目前已经收录超过14万个字符。

Unicode的表示方式：U+XXXX，其中XXXX是4到6位的十六进制数。例如： - 'A' 的码点是 U+0041 - '中' 的码点是 U+4E2D - '😀' 的码点是 U+1F600

但Unicode只定义了码点到数值的映射，没有规定如何在计算机中存储这些数值。这就是UTF（Unicode Transformation Format）的作用。

UTF-8是目前互联网上最常用的Unicode编码方式，它是一种变长编码：

码点范围	字节数	编码格式
U+0000 ~ U+007F	1字节	0xxxxxxx
U+0080 ~ U+07FF	2字节	110xxxxx 10xxxxxx
U+0800 ~ U+FFFF	3字节	1110xxxx 10xxxxxx 10xxxxxx
U+10000 ~ U+10FFFF	4字节	11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

UTF-8的设计非常巧妙： - 与ASCII完全兼容：ASCII字符在UTF-8中只需1字节，与ASCII编码完全相同 - 自同步：任何字节的开始位置都可以被识别，不会因为中间某字节损坏而影响后续字符 - 节省空间：英文字母只占1字节，中文字符占3字节（比UTF-16的2字节稍大，但考虑到英文文本的空间节省，总体效率更高）

示例：

'A' (U+0041)：在第一范围内，编码为 01000001（1字节）
'中' (U+4E2D)：在第三范围内
4E2D 的二进制：0100 1110 0010 1101
去掉U+的前缀得到：100 111000 101101（补齐12位）
按3字节格式填充：11100100 10111000 10101101
十六进制：E4 B8 AD

验证："中"字的UTF-8编码是 E4B8AD，在浏览器开发者工具中可以看到。

1.6.5 编码选择与转换

不同的编码适用于不同的场景：

ASCII：英文为主的文档，不需要中文字符时
GBK/GB18030：中文Windows系统的默认编码
UTF-8：互联网内容（网页、邮件等）的标准编码，跨平台、跨语言的首选
UTF-16：Java、JavaScript、C#等语言内部使用的编码（Windows的API也常用UTF-16）

编码转换的注意事项： 1. 转换时需要知道源编码是什么，否则会乱码 2. 某些字符在目标编码中可能不存在（如将GBK的中文转成ASCII），通常会用'?'或'□'替代 3. 文本文件开头可能有BOM（Byte Order Mark），用于指示是大端序还是小端序，以及编码类型

1.6.6 字符串与编码

在编程中处理字符串时，编码问题经常是bug的来源。

以Python为例：

# Python 3默认使用UTF-8
s = "你好，世界"
print(len(s))  # 输出 6（字符数，不是字节数）
print(s.encode('utf-8'))  # 输出 b'\xe4\xbd\xa0\xe5\xa5\xbd\xef\xbc\x8c\xe4\xb8\x96\xe7\x95\x8c'
print(len(s.encode('utf-8')))  # 输出 18（UTF-8编码占18字节）

以JavaScript为例：

// JavaScript字符串是UTF-16编码
let s = "你好，世界";
console.log(s.length);  // 输出 6
console.log(new TextEncoder().encode(s));  // 输出 Uint8Array [230, 151, 165, 229, 155, 189, 239, 188, 140, 228, 188, 155, 231, 149, 140]

本节小结

字符编码将字符映射为数字，再存储为二进制
ASCII是最早的编码，用7位表示128个字符，只适用于英文
为了支持其他语言，出现了GBK、Big5等地区性编码
Unicode为世界上所有文字分配了唯一的码点
UTF-8是互联网的主要编码，变长设计，与ASCII兼容，节省空间
处理文本时要注意编码一致性，避免乱码

1.7 布尔代数与逻辑门

1.7.1 布尔代数基础

布尔代数（Boolean Algebra）由英国数学家乔治·布尔（George Boole）在19世纪中叶创立，是计算机科学的数学基础。

与普通代数使用实数不同，布尔代数使用布尔值（也称为逻辑值）：只有两个可能的值，通常记为真（True）和假（False），在计算机中常用1和0表示。

1.7.2 基本逻辑运算

布尔代数有三种最基本的运算：

1. 与运算（AND，合取）

也称为逻辑乘，用符号 $\cdot$ 或 $\land$ 表示。运算规则是：只有当所有操作数都为真时，结果才为真。

\[A \land B = \begin{cases} 1 & \text{如果 } A = 1 \text{ 且 } B = 1 \\ 0 & \text{其他情况} \end{cases}\]

2. 或运算（OR，析取）

用符号 $+$ 或 $\lor$ 表示。运算规则是：只要有一个操作数为真，结果就为真。

\[A \lor B = \begin{cases} 1 & \text{如果 } A = 1 \text{ 或 } B = 1 \\ 0 & \text{其他情况} \end{cases}\]

3. 非运算（NOT，否定）

用符号 $\neg$ 或 $\bar{A}$ 表示。运算是取反：真变假，假变真。

\[\neg A = \begin{cases} 1 & \text{如果 } A = 0 \\ 0 & \text{如果 } A = 1 \end{cases}\]

1.7.3 复合逻辑运算

除了三种基本运算，还有几种常见的复合运算：

异或（XOR，排他或）：当两个操作数不同时结果为真，相同时为假。

\[A \oplus B = A \cdot \bar{B} + \bar{A} \cdot B\]

同或（XNOR，等价）：当两个操作数相同时结果为真，不同则为假，是异或的反。

\[A \odot B = \overline{A \oplus B} = A \cdot B + \bar{A} \cdot \bar{B}\]

1.7.4 布尔代数定律

布尔代数遵循一些重要的定律，这些定律可以直接用于逻辑电路的化简：

交换律： $$A + B = B + A$$ $$A \cdot B = B \cdot A$$

结合律： $$(A + B) + C = A + (B + C)$$ $$(A \cdot B) \cdot C = A \cdot (B \cdot C)$$

分配律： $$A \cdot (B + C) = A \cdot B + A \cdot C$$ $$A + (B \cdot C) = (A + B) \cdot (A + C)$$

吸收律： $$A + A \cdot B = A$$ $$A \cdot (A + B) = A$$

德·摩根定律（De Morgan's Laws）： $$\overline{A + B} = \bar{A} \cdot \bar{B}$$ $$\overline{A \cdot B} = \bar{A} + \bar{B}$$

德·摩根定律是布尔代数中特别重要的定律，它表明"与"和"或"在取反时可以相互转换。

1.7.5 逻辑门基础

逻辑门（Logic Gate）是实现布尔运算的电子元件，是数字电路的基本构建单元。

与门（AND Gate）：实现与运算。符号是一个平顶三角形后面跟着一个圆（表示"与"）。有多个输入，一个输出，只有所有输入都为高电平时，输出才为高电平。

或门（OR Gate）：实现或运算。符号是一个圆弧后面跟着一个平顶三角形。有多个输入，一个输出，只要有一个输入为高电平，输出就为高电平。

非门（NOT Gate）：实现非运算，也称为反相器（Inverter）。符号是一个三角形后面跟着一个小圆圈。一个输入，一个输出，输出是输入的反。

与非门（NAND Gate）和或非门（NOR Gate）：分别是与门和非门、或门和非门的组合，输出是AND或OR结果的取反。

异或门（XOR Gate）：实现异或运算。符号与或门相似，但在输入侧多了一条曲线。

1.7.6 组合逻辑电路

由多个逻辑门组成的电路称为组合逻辑电路（Combinational Logic Circuit），其输出仅取决于当前的输入。

加法器（Adder）是组合逻辑电路的典型例子。

半加器（Half Adder）：实现两个一位二进制数相加，产生和（Sum）和进位（Carry）。电路由一个异或门和一个与门组成： - 和 = A XOR B - 进位 = A AND B

全加器（Full Adder）：实现三个一位二进制数相加（包含来自低位的进位）。它由两个半加器和一个或门组成。

多位数加法器由多个全加器级联而成，可以实现任意位数的二进制加法。

1.7.7 时序逻辑电路

与组合逻辑电路不同，时序逻辑电路（Sequential Logic Circuit）的输出不仅取决于当前输入，还取决于之前的输入（即电路的"记忆"功能）。

触发器（Flip-Flop）是时序逻辑电路的基本存储单元。最基本的RS触发器由两个与非门或两个或非门交叉连接而成，可以存储1位数据。

寄存器（Register）由多个触发器组成，可以存储多个位的数据。

计数器（Counter）是一种特殊的时序逻辑电路，可以对输入脉冲进行计数。

本节小结

布尔代数使用真/假（1/0）两种值，有与、或、非三种基本运算
异或、同或等复合运算可以由基本运算组合而成
布尔代数定律包括交换律、结合律、分配律、吸收律和德·摩根定律
逻辑门是实现布尔运算的电子元件，包括与门、或门、非门等
组合逻辑电路的输出只取决于当前输入，加法器是其典型应用
时序逻辑电路具有记忆功能，触发器是其基本存储单元

本章小结

本章介绍了计算机中数据表示和处理的基础知识，主要包括以下几个部分：

进制与转换：计算机使用二进制（0和1），八进制和十六进制是为了方便表示二进制而引入的。不同进制之间可以相互转换，理解权值概念是进行进制转换的关键。
二进制运算：包括算术运算（加、减、乘、除）和位运算（与、或、异或、取反、移位）。计算机通过补码实现减法变加法。
整数编码：原码、反码、补码是三种有符号数的表示方法。现代计算机采用补码表示有符号整数，因为它解决了0的表示不唯一的问题，并使得加减运算可以直接进行。
浮点数编码：IEEE 754标准规定了浮点数的表示方法。单精度浮点数由1位符号、8位指数、23位尾数组成，采用偏移码和隐藏位技术。浮点数精度有限，运算存在误差。
字符编码：ASCII是最初的字符编码，只支持英文字母。Unicode为世界上所有文字分配了唯一码点，UTF-8是互联网最常用的编码，采用变长设计，与ASCII兼容。
布尔代数与逻辑门：布尔代数是数字电路的数学基础，与、或、非三种基本运算可以组合成任意复杂的逻辑功能。逻辑门是实现布尔运算的电子元件，由它们组成加法器等组合逻辑电路和触发器等时序逻辑电路。

思考与练习

进制转换
将二进制数 $1101011_2$ 转换为十进制、八进制和十六进制。
将十进制数 $1023_{10}$ 转换为二进制。
补码运算
8位补码能表示的整数范围是多少？
计算8位补码 $11111111 + 00000001$ 的结果（用补码解释），并说明发生了什么。
浮点数理解
用IEEE 754单精度表示法表示十进制数 $3.14159$（约等于圆周率）。
解释为什么 0.1 + 0.2 != 0.3 在大多数编程语言中成立。
字符编码
'A' 和 'a' 的ASCII码分别是65和97，计算它们的二进制表示，并解释为什么小写字母的ASCII码比对应的大写字母大32。
UTF-8编码中，中文字符通常占3个字节，请说明为什么需要多个字节来表示中文。
逻辑化简
使用布尔代数定律化简表达式：$F = A \cdot B + \bar{A} \cdot C + B \cdot C$
给出化简后的结果，并用真值表验证。
溢出分析
用8位有符号整数计算 $100 + 50$，判断是否溢出；如果溢出，说明原因。
如果改用8位无符号整数计算同样的表达式，结果是多少？

位位置	5	4	3	2	1	0
位值	1	0	1	1	0	1
权值	\(2^5\)	\(2^4\)	\(2^3\)	\(2^2\)	\(2^1\)	\(2^0\)
贡献	32	0	8	4	0	1

类别	最小值	最大值
规格化正数	\(2^{-126} \approx 1.18 \times 10^{-38}\)	\((2 - 2^{-23}) \times 2^{127} \approx 3.4 \times 10^{38}\)
非规格化正数	\(2^{-149} \approx 1.4 \times 10^{-45}\)	略小于最小规格化正数

第一章 进制与编码

学习目标

1.1 进制的概念

1.1.1 什么是进制

1.1.2 进制的表示方法

1.1.3 进制的权值

1.1.4 二进制的特点

本节小结

1.2 进制转换

1.2.1 十进制转换为其他进制

1.2.2 其他进制转换为十进制

1.2.3 二进制与八进制、十六进制的转换

1.2.4 常见进制对照表

1.2.5 小数部分的转换

本节小结

1.3 二进制运算

1.3.1 二进制加法

1.3.2 二进制减法

1.3.3 二进制乘法

1.3.4 二进制除法

1.3.5 位运算

1.3.6 移位运算

本节小结

1.4 数据编码：整数表示

1.4.1 为什么需要原码、反码、补码

1.4.2 原码

1.4.3 反码

1.4.4 补码

1.4.5 补码的直观理解

1.4.6 整数溢出

本节小结

1.5 浮点数编码：IEEE 754

1.5.1 浮点数的由来

1.5.2 IEEE 754标准概述

1.5.3 浮点数的结构

1.5.4 规格化浮点数

1.5.5 特殊值

1.5.6 浮点数的取值范围和精度

1.5.7 浮点数的误差

本节小结

1.6 字符编码

1.6.1 为什么需要字符编码

1.6.2 ASCII码

1.6.3 扩展编码

1.6.4 Unicode与UTF-8

1.6.5 编码选择与转换

1.6.6 字符串与编码

本节小结

1.7 布尔代数与逻辑门

1.7.1 布尔代数基础

1.7.2 基本逻辑运算

1.7.3 复合逻辑运算

1.7.4 布尔代数定律

1.7.5 逻辑门基础

1.7.6 组合逻辑电路

1.7.7 时序逻辑电路

本节小结

本章小结

思考与练习

第一章进制与编码