陈东的博客

# CSAPP

本文是我看 CMU-213 做的笔记总结。

# Lecture 02

视频中一共讲了下面这些知识点，比较基础，书上都有。有基础的可以跳着看视频，然后过一遍书。

# 布尔代数

【textbook 2.1.1】因为二进制写起来太长太繁琐，所以我们通常用 16 进制来表示，对照表要背一下。

【textbook 2.1.6】介绍了与、或、非、异或四种布尔代数运算。

【textbook 2.1.7】在 C 语言中分别对应 & | ~ ^ 这四个运算符。

【textbook 2.1.8】C 语言初学者很容易将 && 和 & 搞混。

# 移位操作

【textbook 2.1.9】算术右移在左边补符号位、逻辑右移在左边补 0。算术左移、逻辑左移没区别，都是在右边补 0。

# 整数的二进制表示

【textbook 2.2】直接看书吧。

# Lecture 03

# 整数加法

【textbook 2.3.1】无符号数相加，两个 w 位的整数相加，结果可能需要 w+1 位来存，如果存不下我们会把高位截断这就叫做 overflow

【textbook 2.3.2】有符号数相加，因为现在普遍用补码表示有符号数，所以我们讨论的就是补码相加。补码相加分为正溢出、负溢出两种情况。我们还要学会如何检测发生了溢出。

# 整数乘法

【textbook 2.3.4】两个 w 位的整数相乘，结果可能需要 2*w 位来存，也会发生 overflow

【textbook 2.3.5】补码乘法，检查乘法是否溢出会更困难一些。

【textbook 2.3.6】乘以 2、4、8、16 分别相当于左移 1、2、3、4 位，编译器经常这样优化代码，因为乘法指令比移位指令要慢。

【textbook 2.3.7】除以 2 的幂相当于右移。这部分比较复杂，建议好好啃一下课本。

整数除法的情况更加复杂

  • 右移分为算术右移、逻辑右移
  • 对于正数需要向下取整，对于负数需要向上取整，总之就是向 0 的方向取整

我们在补码上执行除法/右移，会发现它总是向下取整。这样会得到 -1 / 2 = -2 的错误结果。因此编译器会在移位前做一个 biasing。C 语言中 -1 / 2 答案是 -1，但是在 Python 中答案是 -2，看起来 Python 没有做 biasing。

# 无符号数经常导致的 bug

这部分内容书上好像没有。

视频里面是说 unsigned 有个很坑的 overflow: 0 - 1 = UMAX，这导致了下面这两个例子中那样难以发现的 bug。

unsigned i;
// 会死循环
for (i = cnt - 2; i >= 0; i--)
  a[i] += a[i+1];

#define DELTA sizeof(int)

int i;
// DELTA 是 unsigned，i 被隐式转换为 unsigned
for (i = CNT; i - DELTA >= 0; i -= DELTA)
  ...

下面这段代码看起来非常难懂，但确实是没有 bug 的，总之慎用 unsigned。

unsigned i;
// 当 i 向下溢出的时候，i = UMAX，于是循环终止
for (i = cnt - 2; i < cnt; i--)
  a[i] += a[i+1];