Week 2 notes

二进制数以 0，1 的组合表示各式各样的数据：n 位二级制数拥有 $2^n$ 的组合数量。

二级制按照如下的规则转化为十进制：

• 从左到右，从 0 开始，每一位的权为 $2^n$
• 十进制的结果等于二进制数的带权和

比如下面的例子, 101 转化的的结果是 5：



也就是如果有 k 位 Bit,最大能表达的数字为：

$$ 1 + 2 + 4 +...+2^{k-1} = 2^k - 1 $$

计算机中字的长度是有限的，因此表示的范围也是有限的。理想情况下，一个 8 位的字可以表示 $2^8 = 256$ 个数字；但实际上，如果需要表示负数，那么 8 位的其中一位就会作为符号位，这样 8 bit 只能表示 0-127

按之前转化的逆顺序：

• 找出当前 10 进制中最大的，可以通过 2^n 计算出的数
• 从当前数中减去该数
• 重复上面两步，直到只剩 1($2^0$)

这个过程相当于是在还原二级制构造十进制的过程。因此，之前能找出来的数证明其对应的 Bit 上都是 1，反之都是 0。以 87 位例：

二进制的加法与十进制类似，按位相加：



如果遇到 1+1 的情况，则进位。进位是逢 2 进 1：

如果最后一位相加也需要进位，此时结果长度超出了字的长度。我们称该情况为加法溢出（overflow）。解决的方式是：忽略所有额外的进位。从计算机的角度来考虑，如果加法超出了字长的限制，那么我们做的加法，就不再是真正的加法了。

从这个思路出发，Adder 的设计分为：

• Half Adder：负责两个 Bit 的相加
• Full Adder：负责三个 Bit，即两个 Bit 与 carry 的相加

Half Adder 完成的工作是将两个 Bits 相加。那么：

• 输入：两个 bits
• 输出：一个 bit （和），一个 carry（进位）

需要注意的是，两个 Bits 相加只和当前的 Bit 有关。只要是 1 + 1，那么进位就是 1，结果就是 0。因此，我们可以得到如下的真值表：

Full Adder 完成的工作是将两个 Bits 与 carry 位相加：

• 输入：bit a, b, c
• 输出：sum, carry

其真值表也非常容易得到：

这个 adder 由一系列的 half adder 和 full adder 组成。准确的来说，是 15 个 full adder 与 1 个（最右边的）half adder 组合在一起，组成了 16 bits 的，带进位的加法计算器。

表示负数的方式有三种：

• signbit（原码）
• Complement （补码）

这种方式使用二进制的最高位作为符号位，以此来区分正负数。其他位不变，比如：

000 -> 0 100 -> -0
001 -> 1 101 -> -1
010 -> 2 110 -> -2
011 -> 3 111 -> -3

• -0 的定义，它与 0 的区别无法解释
• 加减法无法处理。比如 1 + (-1)，也就是 001 + 101, 结果是 110，为 -2, 不是 0