======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(原码)=== 这种方式使用二进制的最高位作为符号位,以此来区分正负数。其他位不变,比如: 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'' ===2's Complement(补码)=== 这种方式下,所有的负数都用 bits 可以表示数字的总数来减去负数对应的整数,即: $$2^n-x$$ 比如: // 4 bits, total numbers: 2^4 = 16 3 -> 0011 // decimal -3 -> 16 - 3 = 13 -> 2^3 + 2^2 + 2^0 -> 1101 这种情况下,正数的表达范围为 $[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 $$ 观察一下上面的变形,可以发现: 1 -> 1 2^n - 1 -> 11111....1111 那么也就是说,$-x$ 的实际结果,等于所有 bits 都是 $1$ 的数减去 $x$ 对应的二进制,再加上一。比如 $-2$,如果以 4 bits 的 二进制表示,就是: 16 - 2 -> 15 - 2 + 1 -> 1111 - 0010 + 1 -> 1101 + 1 -> 1110 从形式上来看,$x$ 的负数结果实际上是直接将 $x$ 的二进制**按位翻转**后再**加上一**得到的。 ====Arithmetic Logic Unit==== //Arithmetic Logic Unit// (ALU) 在冯诺依曼架构中充当了很重要的角色。具体的来说: * ALU 扮演的是函数的角色,也就是接受输入,然后按指定的方法计算结果的的计算单元。 * ALU 对应的函数是**提前定义**的,**算术**或**逻辑**运算的一种(或是这两者的组合) ALU 的设计在硬件和软件中均可实现。硬件实现下,ALU 的速度会更快,但成本会更高。 ===实例: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 输出位的真值表==