波仔
🧮 第8章 算法和计算机
📄 一句话概括

与、或、异或、非四块积木， 两个输入只有 4 种组合，一共 16 个格子——计算机里所有判断都是这 16 个格子拼出来的。 德摩根定律：把非号推进括号，与和或互换。 位运算把八位当八个开关：权限标志、功能开关、图像通道掩码，本质都是它。

📝 本章和前面几章的关系

这一节是全书最后一节，讲计算机的另一半地基。 第 8 章前几节讲「数怎么存」，这一节讲「判断怎么做」。 真值表只有 16 个格子，看着少，但所有 if 语句、所有电路、所有查询条件，都是它拼出来的。 顺便要说清教材里一个名字上的坑——「或非」那一节的表其实是异或。

一、四种基本运算的真值表

两个输入 A 和 B，各有 0 和 1 两种可能，所以只有 4 种组合。

A B A 与 B A 或 B A 异或 B 非 A
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 0
1 1 1 1 0 0

四种运算各 4 个结果，一共 16 个格子。计算机里所有的判断，都是从这 16 个格子拼出来的。 记法很简单：与要求两个都是 1，或只要有一个是 1，异或要求两个不一样，非就是反过来。 其中异或最容易被忘。它的意思是「不同为真」——1 和 0 得 1，1 和 1 得 0。

异或有个好玩的性质：同一个数异或两次会还原。第 4.5 那个「不借盒子交换变量」的异或法， 靠的就是这一条。

二、教材这里有个名字上的坑

教材讲「或非」的那一小节把这一列叫「或非」（演示里按原书节号写作 8.8），但从真值表看， 1 和 0 得 1、1 和 1 得 0 正是异或。 真正的「或非」是「先或、再取反」：0 和 0 得 1，其余三个都得 0。和这里的表不一样。 所以演示里那句提醒很到位：名字容易混，认表最靠得住。

这件事本身也是个提醒：术语是约定，真值表是事实。两处对不上时，以能验证的那一边为准。 这条经验在整本书里反复出现：教材说一阶精度、实测是二阶；教材说某个数、实测不一样。 能跑出来的东西，优先信跑出来的。

三、德摩根定律：把否定推进括号里

两条定律，一句话说完：把非号推进括号，与和或互换。 非(A 且 B) 等于 (非 A) 或 (非 B)；非(A 或 B) 等于 (非 A) 且 (非 B)。

A B 非(A 且 B) (非 A) 或 (非 B) 两边一样吗
0 0 1 1 一样
0 1 1 1 一样
1 0 1 1 一样
1 1 0 0 一样

四种组合全部一样，所以定律成立。这不是「看起来像」，是逐一验证过的。 多推一层就再换一次：非(非 A) 变回 A，非(A 且 (非 B)) 变成 (非 A) 或 B。 它真正的用处在写判断条件。 「不是（已付款 且 已发货）」可以改写成「未付款 或 未发货」——两句话意思一样， 但第二句更好写代码，也更好读。

四、位运算：把八位当成八个开关

逻辑运算用在单个 0 和 1 上叫逻辑运算，用在八个位上叫位运算。同一套规矩，只是并排做八次。 以 x = 10110100（十进制 180）为例：

想干什么 怎么写 结果
看第 3 位是 0 还是 1 右移两位，再和 1 相与 1
把第 1 位置 1 x 和 0b00000010 相或 10110110
把第 8 位清 0 x 和 0b01111111 相与 00110100
判断奇偶 x 和 1 相与 0
乘 2 x 左移一位 360
除 2 x 右移一位 90

最后两行值得记：左移一位等于乘 2，右移一位等于除 2（丢掉余数）。 早年编译器不会优化乘法时，程序员就是这么写乘二的。 现在编译器比人聪明，写 x * 2 就行——让它替你决定要不要移位。 但「用位运算表示开关」这件事没变：权限标志、功能开关、图像通道掩码， 本质都是把一串 0 和 1 当一排开关用。一个字段存八个开关，省空间也省查询。

五、全书收个尾

第 8 章整章讲的都是「电脑眼里的数据长什么样」——二进制的写法、正负数的补码、逻辑运算。 而前面七章讲的算法，最后都要落成这些 0 和 1 的加减与判断。 所以算法和计算机是一件事的两头：一头是怎么想，一头是怎么存。两头都通了， 才知道自己写的代码在机器上到底发生了什么。

回头看这八章：先认识算法（第 1 章），再认识数据（第 2 章），然后是数据的摆放（第 3 章）、 基础套路（第 4 章）、排序（第 5 章）、搜索（第 6 章）、其他算法（第 7 章）， 最后落到机器表示（第 8 章）。 这份路线有个特点：每一章都在给下一章提供零件。没有第 3 章的树，第 6 章的二分就讲不透； 没有第 4 章的循环，第 5 章的排序就写不出来。 最后留一句最实在的：算法的本事不在背，在估算。看到一个方案，能立刻判断「这个规模会不会崩」， 比记住七种排序的复杂度有用得多。

六、动手 Demo：四张真值表，加上把八位当开关

先把与、或、异或、非四种运算的 4 种组合全跑一遍。 再验证德摩根定律：两边算出来是不是真的一样。 最后拿 180 试几个位运算：取某一位、置某一位、清某一位、乘二除二。

for a in (0, 1):
    for b in (0, 1):
        print(a, b, a & b, a | b, a ^ b, 1 - a)

for a in (0, 1):
    for b in (0, 1):
        print(a, b, 1 - (a & b), (1 - a) | (1 - b))

x = 180
print(bin(x))
print('第 3 位', (x >> 2) & 1)
print('置第 1 位', bin(x | 0b00000010))
print('清第 8 位', bin(x & 0b01111111))
print('奇偶', x & 1)
print('乘二', x << 1, '除二', x >> 1)

实跑输出：

--------------------------------------------------------------------
逻辑运算与德摩根定律
--------------------------------------------------------------------


  ① 四种基本运算的真值表
  --------------------------------------------------------------------

| A | B | A 与 B | A 或 B | A 异或 B | 非 A |
|:---:|:---:|:---:|:---:|:---:|:---:|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |

  前两列是两个输入，后四列是结果。
  两个输入只有 4 种组合，四种运算各 4 个结果，一共 16 个格子——计算机里所有的判断，
  都是从这 16 个格子拼出来的。
  ! 教材第 8.8 节把它叫「或非」，但从真值表看，「1 和 0 得 1、1 和 1 得 0」正是异或（XOR）。
  名字容易混，认表最靠得住——输入相同得 0，输入不同得 1，这就是异或。

  ② 德摩根定律：把否定推进括号里
  --------------------------------------------------------------------

| A | B | 非(A 且 B) | (非 A) 或 (非 B) | 两边一样吗 |
|:---:|:---:|:---:|:---:|---|
| 0 | 0 | 1 | 1 | 一样 |
| 0 | 1 | 1 | 1 | 一样 |
| 1 | 0 | 1 | 1 | 一样 |
| 1 | 1 | 0 | 0 | 一样 |

  真跑四种组合，全部一样。所以：非(A 且 B) 等于 (非 A) 或 (非 B)
  同理：非(A 或 B) 等于 (非 A) 且 (非 B)
  记法很简单：把非号推进括号，与和或互换。多推一层就再换一次。
  用处在写判断条件。
  「不是（已付款 且 已发货）」改写成「未付款 或 未发货」，两句话意思一样，但第二句更好写代码，
  也更好读。

  ③ 位运算：把八位当成八个开关
  --------------------------------------------------------------------
  x = 10110100（十进制 180）

| 想干什么 | 怎么写 | 结果 |
|---|---|---|
| 看第 3 位是 0 还是 1 | (x >> 2) 再和 1 相与 | 1 |
| 把第 1 位置 1 | x 和 0b00000010 相或 | 10110110 |
| 把第 8 位清 0 | x 和 0b01111111 相与 | 00110100 |
| 判断奇偶 | x 和 1 相与 | 0 |
| 乘 2 | x << 1 | 360 |
| 除 2 | x >> 1 | 90 |

  最后两行值得记：左移一位等于乘 2，右移一位等于除 2（丢掉余数）。
  早年编译器不会优化乘法时，程序员就是这么写乘二的。
  现在编译器比人聪明，写 x * 2 就行。
  但「用位运算表示开关」这件事没变——权限标志、功能开关、图像通道掩码，
  本质都是把一串 0 和 1 当一排开关用。

  ④ 一句话收尾
  --------------------------------------------------------------------
  第 8 章整章讲的都是「电脑眼里的数据长什么样」。
  而前面七章讲的算法，最后都要落成这些 0 和 1 的加减与判断。
  所以算法和计算机这两件事，是一件事的两头：一头是怎么想，一头是怎么存。
  两头都通了，才知道自己写的代码到底在机器上发生了什么。

①第一段六列：a、b、与、或、异或、非 a。1 - a 就是「非」，因为 0 变 1、1 变 0。 ②第二段是德摩根：1 - (a & b) 对 (1 - a) | (1 - b)，四行全部相等。 ③(x >> 2) & 1 是「把要看的位移到最低位，再用 1 把其他位盖掉」。这是取某一位的标准写法。 ④置位用或（有一就变一），清位用与（和 0 相与必得 0）。这两个动作是所有开关操作的基础。

30 秒实验

  1. 把异或那一列和「或非」的真值表对比一下，看差在哪。
  2. 用位运算实现「交换两个整数」，不借第三个变量（第 4.5 讲的异或法）。
  3. 想一个你见过的「一个字段存多个开关」的例子（比如权限、星期、通知设置）。

常见误区

  1. 「或非就是异或。」不是。或非是「先或再取反」，真值表是 1000；异或是 0110。
  2. 「位运算过时了，编译器都会优化。」优化的是乘除，「一个字段存八个开关」这种用法一直在。
  3. 「德摩根定律只是化简，不影响结果。 」对，它不改结果只改写法——所以改写之后原来的测试应该全部还能过。
自测三问（点开对答案） 1. 与、或、异或三者的区别是什么？ —— 与要两个都是 1；或只要有一个是 1；异或要两个不一样。 2. 德摩根定律怎么记？ —— 把非号推进括号，与和或互换。多推一层就再换一次。 3. 要清掉某一位，用哪种运算？ —— 与。把要清的那一位设成 0、其余设成 1，相与之后那一位一定是 0。

全书八章到此结束。 想接着往下走，可以去索引页看看配套课程：数据结构、操作系统、计算机网络，都能接在这本后面。

相关笔记