======Boolean Arithmetic and the ALU======
//Week 2 notes//
----
====Binary Numbers====
二进制数以 ''0''，''1'' 的组合表示各式各样的数据：''n'' 位二级制数拥有 $2^n$ 的组合数量。
===二进制表示数字===
==Binary to Decimal==
二级制按照如下的规则转化为十进制：
  * 从左到右，从 0 开始，每一位的权为 $2^n$
  * 十进制的结果等于二进制数的带权和

比如下面的例子, ''101'' 转化的的结果是 ''5''：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:2_to_10.svg?350 |}}
\\ \\ 
也就是如果有 ''k'' 位 Bit,最大能表达的数字为：

$$
1 + 2 + 4 +...+2^{k-1} = 2^k - 1
$$
==Fixed word size==
计算机中字的长度是有限的，因此表示的范围也是有限的。理想情况下，一个 ''8'' 位的字可以表示 $2^8 = 256$ 个数字；但实际上，如果需要表示负数，那么 ''8'' 位的其中一位就会作为符号位，这样 8 bit 只能表示 ''0-127''
==Decimal to Binary==
按之前转化的逆顺序：
  * 找出当前 10 进制中最大的，可以通过 ''2^n'' 计算出的数
  * 从当前数中减去该数
  * 重复上面两步，直到只剩 ''1''($2^0$)
这个过程相当于是在还原二级制构造十进制的过程。因此，之前能找出来的数证明其对应的 Bit 上都是 ''1''，反之都是 ''0''。以 ''87'' 位例：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:10_to_2.svg?400 |}}
\\ \\ 
====Binary Addition====
二进制的加法与十进制类似，按位相加：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:addition.jpg?150 |}}
\\ \\ 
如果遇到 ''1+1'' 的情况，则进位。进位是逢 ''2'' 进 ''1''：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:addition_2.jpg?200 |}}
===overflow===
如果最后一位相加也需要进位，此时结果长度超出了字的长度。我们称该情况为加法溢出（//overflow//）。解决的方式是：**忽略**所有额外的进位。从计算机的角度来考虑，如果加法超出了字长的限制，那么我们做的加法，就不再是真正的加法了。
===Adder 的设计===
从这个思路出发，Adder 的设计分为：
  * Half Adder：负责两个 Bit 的相加
  * Full Adder：负责三个 Bit，即两个 Bit 与 carry 的相加
==Half Adder==
//Half Adder// 完成的工作是将两个 Bits 相加。那么：
  * 输入：两个 bits ''x'', ''y''
  * 输出：一个 bit （和），一个 carry（进位）
需要注意的是，两个 Bits 相加只和当前的 Bit 有关。只要是 ''1 + 1''，那么进位就是 ''1''，结果就是 ''0''。因此，我们可以得到如下的真值表：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:half_adder.svg?240 |}}
==Full Adder==
//Full Adder// 完成的工作是将两个 Bits 与 carry 位相加：
  * 输入：bit a, b, c
  * 输出：sum, carry
其真值表也非常容易得到：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:full_adder.svg?270 |}}
==Multi-bit Adder(16bits)==
这个 adder 由一系列的 half adder 和 full adder 组成。准确的来说，是 15 个 full adder 与 1 个（最右边的）half adder 组合在一起，组成了 16 bits 的，带进位的加法计算器。
====Negative Numbers====
表示负数的方式有三种：
  * signbit（原码）
  * Complement （补码）
===Signed Bit（原码）===
这种方式使用二进制的最高位作为符号位，以此来区分正负数。其他位不变，比如：
<code cil>
000 -> 0 100 -> -0
001 -> 1 101 -> -1
010 -> 2 110 -> -2
011 -> 3 111 -> -3
</code>
这种方法通常不会采用，有几个大的缺点：
  * ''-0'' 的定义，它与 ''0'' 的区别无法解释
  * 加减法无法处理。比如 ''1 + (-1)''，也就是 ''001 + 101'', 结果是 ''110''，为 ''-2'', 不是 ''0''
===2's Complement（补码）===
这种方式下，所有的负数都用 bits 可以表示数字的总数来减去负数对应的整数，即：
$$2^n-x$$
比如：
<code CIL>
// 4 bits, total numbers: 2^4 = 16
 3 -> 0011
// decimal
-3 -> 16 - 3 = 13 -> 2^3 + 2^2 + 2^0 -> 1101
</code>
这种情况下，正数的表达范围为 $[0, 2^{n-1} - 1]$，负数的表达范围为 $[-1, -2^{n-1}]$
==补码的优势==
使用补码表示负数可以将负数的加法（减法）转化为加法：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:2s_complement_add_neg.jpg?250 |,}}
根据上面的例子，这个过程分为了三步：
  - 求出负数的补码结果（正数，比如 $-2 = 16 - 2 = 14$）
  - 将得到的正数转换为二级制相加
  - 当存在 overflow 时，溢出位将被自动丢弃，比如此处 $14+13=27$，丢弃溢出位后结果为 $27-16 = 11$
  - $11$ 是以补码形式，根据公式，负数的表现形式为：$2^4 - positiveNumber = 11$。可以得到正数的值为 $5$，因此 $11$ 对应的负数为 $-5$
===计算 -x===
上面计算负数的过程是将二进制转化为十进制来进行的。实际上，利用补码公式的变形，就可以很轻松的用二进制直接计算负数：
$$
2^n-x = 1 +(2^n-1) -x
$$
观察一下上面的变形，可以发现：
<code CIL>
1 -> 1
2^n - 1 -> 11111....1111
</code>
那么也就是说，$-x$ 的实际结果，等于所有 bits 都是 $1$ 的数减去 $x$ 对应的二进制，再加上一。比如 $-2$，如果以 4 bits 的
二进制表示，就是：
<code CIL>
16 - 2
-> 15 - 2 + 1
-> 1111 - 0010 + 1
-> 1101 + 1
-> 1110
</code>
从形式上来看，$x$ 的负数结果实际上是直接将 $x$ 的二进制**按位翻转**后再**加上一**得到的。
====Arithmetic Logic Unit====
//Arithmetic Logic Unit// (ALU) 在冯诺依曼架构中充当了很重要的角色。具体的来说：
  * ALU 扮演的是函数的角色，也就是接受输入，然后按指定的方法计算结果的的计算单元。
  * ALU 对应的函数是**提前定义**的，**算术**或**逻辑**运算的一种（或是这两者的组合）
<WRAP center round box 100%>
ALU 的设计在硬件和软件中均可实现。硬件实现下，ALU 的速度会更快，但成本会更高。
</WRAP>
===实例：Hack ALU===
本课例子（HACK ALU）：
  * 接收两个 16 bits 的输入
  * 得到一个 16 bits 的输出和两个 1 bits 的输出。
  * 实现了一系列的（总共18个）**基础**函数
  * 调用哪个函数通过结构图正上方的 6 个 1 bit 的输入来决定。
其结构图如下：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:hack_alu.jpg?300 |}}
\\ 
==控制位与 16bits 输出位的真值表==
Hack ALU 常用的 18 种运算的真值表如下：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:hackalu_truetable.jpg?400 |}}
\\ 
上面 6 个控制位均在 0 和 1 时代表了两种不同的运算：
\\ \\ 
{{ :cs:comp_n_arch:courses:fnti_i:contorl_bits_alu.svg?300 |}}
\\ \\ 
整个计算过程从左到右进行运算，前面的运算结果会作为下一次的算子参与新的运算。比如下面的例子：

<code CIL>
// input
x = 0010
y = 1011

// calculation: y - x
// control bits sequence from the turth table
0 0 0 1 1 1

// compute process

zx = 0 // do nothing
x = 0010
y = 1011

zy = 0 // do nothing 
x = 0010
y = 1011

zy  = 0 // do nothing
x = 0010
y = 1011

ny = 1 // y = !y
x = 0010
y = 0100

f = 1 // out = x + y
x = 0010
y = 0100
out = 0110

no  = 1 // out  = !out
out = 1001
</code>
==Add16：串行实现==
  * ''0'' bit 使用 half adder 计算
  * 之后只需要将前一位计算的 carry 交给下一个Full adder 即可
==Add16：Carry-ahead==
之前的方法非常慢，必须等到前一个 adder 的结果出来之后才能下一步。我们可以通过 Carry-ahead 的方法进行 carry 位的并行计算。
可以观察到的是，当前 adder 中送到下一个 carry 位是可以根据如下的情况来判断的：
  * 如果参与计算的 bits ''a'', ''b'' 都是 1，那么无论前一个 adder 传递来的 carry 位是什么，当前 adder 的 carry 位一定是 1，也就是 ''a and b''
  * 如果参与计算的 bits 中存在一个 1，且前一位的 carry bit ''ci'' 是 1，那么当前 adder 的 carry 位是 1。判断条件为 ''(a or b) and ci''
这里的第一部分(''a and b'')被称为 //Generate// 位（//G//），第二部分(''a or b'')被称为 //Propagate// 位（P）。也就是说当前 carry 位的值实际上取决于以下的表达式：
$$C_{i+1} = G_{i}∨(P_{i} ∧C_{i})$$
利用这个公式，我们可以对每一位的 $C_i$ 进行展开。也就是说，只要已知所有的 ''a'', ''b''，以及 ''0'' 位的 carry，那么所有的 adder 都可以直接对本位的 carry 进行计算，
比如第二位的 carry 公式就可以展开为：
$$C_2=G_1​∨(P_1∧G_0)​∨(P_1∧P_0​∧C_0))$$
==其他实现上的一些细节==
  * ''Mux16'' 是 ''if / else'' 的硬件实现，使用 ''sel'' 位来作为条件输入
  * 验证某个输出是否小于 0 只需验证其最高位，比如 ''out[15]'' 为 1 则该数为负
  * 验证某个输出是否等于 0 需要使用 ''OrNWay'' 对所有 bits 进行按位 ''Or''。这样计算后：
    * 如果有任意 bit 为 1，那么 Or 的结果都为 1。此时输出是不等于 0 的，如果再将其翻转（//Not//）再输出至是否相等的 bit，此时为 0，也就是不相等。
    * 反之，按位 Or 全为 0，翻转后结果为 1，说明相等。