数据的表示与运算

进制表示

计算机内部对数据的编码方式均为二进制编码

$K$ -进制统一表示的公式为

$(A)_k = \sum_{i=n}^{-m} K_ir^i$

进制间的转换

十进制与二进制之间通常使用短除法

2 |_ 13
2 |_  6  ... 1
2 |_  3  ... 0
2 |_  1  ... 1
      0  ... 1

结果: (13)_10 = (1101)_2

二进制转换为八进制/十六进制使用分组法

===八进制===
11011010-->11 011 010->332
===十六进制===
11011010-->1101 1010--> DA

定点数的编码

生活中的带有符号的数称为真值，符号数字化的数称为机器数

定点小数与定点整数表示

对于数字 $X=x_0x_1\cdots x_n$
作为定点小数表示为

x_0(符号位) 0.x_1x_2...x_n

作为定点整数表示为

x_0(符号位) x_1x_2...x_n

浮点数表示中的尾数是一种类似定点小数表示的方式，但是它整数部分始终为1.对于尾数 $X=x_1\cdots x_n$

1.x_1x_2\cdots x_n

机器码的编码方式

对于一个 $n$ 位带符号机器数，通过 $0\sim 2^{n+1}$ 编码。

原码表示

原码的第一位为符号位置，当真值为正时, 第一位为0，反之为1. 后面填入真值的绝对值

假设二进制数 X=-10101001
则原码为
[X]原=110101001

补码表示

补码的第一位也为符号位，当真值为正时, 第一位为0，反之为1。后面填入上界下探的距离作为补码 $2^{n+1}-|x|$ ，因此补码和真值的二进绝对值是模 $2^{n+1}$ 同余的。

变形补码(模4补码)
模4补码采用两个符号位进行，00表示正数, 11表示负数。左符表示符号位，右符表示溢出位。

正数首位进位后发生溢出
00+00+01=01

负数补码进位--真值不足以进位，发生溢出
11+11=110->10

移码表示

将 $-2^n\sim 2^n$ 整体平移到 $0\sim 2^{n+1}$ , 每一个元素都加 $2^n$

C语言类型转换

short 短整型变量，16位--2字节
int 整型变量，32位--4字节
long 长整型变量, 64位--8字节(64位系统)/ 32位--4字节(32位系统)
char 字符串变量, 8位--1字节，使用无符号整数表示

运算方法与电路

一位全加器

对某一位的加数与进位进行加法。当前位的加法满足异或加法

$A\oplus B = (\neg A \wedge B)\vee (A\wedge \neg B)$

$S_i = (A_i\oplus B_i)\oplus C_{i-1}$

进位满足: $A_i$ 与 $B_i$ 进位，或 $A_i$ 与 $B_i$ 的和与 $C_{i-1}$ 进位

$C_i = (A_i\wedge B_i)\vee ((A_i\oplus B_i)\wedge C_{i-1})$

串行进位加法器将多个加法器进行串联，将进位端首尾连接。

带标志加法器与ALU

带标志加法器在串行进位加法器的基础上添加了加法特征值：

OF 有符号数的溢出判断
SF 最高有效位
CF 无符号数的溢出判断(进位/借位标志)
ZF 零标志数

OF有符号数的溢出判断是基于符号位与最高有效位共同决定的

$\text{OF} = C_n\oplus C_{n-1}$

CF无符号数的溢出判断基于最高位进位

$\text{CF} = C_n = C_n\oplus 0$

算术逻辑单元ALU

ALU实现通过ALUop 标定实现对于加法/与/或运算的控制。ALUop是一个二位标志符，00输出输入值的与运算, 01输出输入值的或运算，10输出输入值的加法运算。最后通过 多路选择器(MUX) 根据ALUop输出结果

定点数的移位

逻辑移位

对于一个二进制数 $X=\overline{x_0x_1\cdots x_n}$ ，满足

$\begin{cases} 2\cdot X = \overline{x_0x_1\cdots x_n 0 } \overset{\text{溢出}}{\longrightarrow} \overline{x_1x_2\cdots x_n 0}\\ X / 2 = \overline{0x_0x_1\cdots x_{n-1}. x_n}\overset{\text{舍弃}}{\longrightarrow } \overline{0x_0x_1\cdots x_{n-1}} \end{cases}$

这样的直接移位方式称为逻辑移位，用于无符号整数的移位

左移时，如果最高有效位为1，则发生了溢出

算术移位

算术移位需要考虑有符号数的符号位，右移压入的首位符号与原符号位相同，而不是直接输入0

如果最低位舍弃的元素为1，会影响有符号数的表示精度

定点数的加减法运算

定点数的加法运算通过串行进位加法器就可以实现，但是对于减法需要进行一套新的语义设置。

在补码意义下，加减法总是模 $2^{n+1}$ 同余的，因此

$\begin{cases} [x+y]_{\text{补}} = [x]_{\text{补}}+[y]_{\text{补}} &(\mathrm{mod} 2^{n+1} )\\ [x-y]_{\text{补}} = [x]_{\text{补}}+[-y]_{\text{补}} &(\mathrm{mod} 2^{n+1} )\\ \end{cases}$

在减法运算输入的前面经过一个判断的反相器，控制指令Sub基于加减法判断是否对输入的信号进行反向。反向后的减数作为其相反数输入加法器与被减数相加。

定点数的乘除法运算

定点数乘法的实现和常规真值的乘法是类似的，分为三个步骤:

乘数和另一个乘数的数位逐位相乘。
将对应的第 $i$ 位的乘法结果左移 $i-1$ 次。
将左移的结果相加

简单串行乘法器的设计:
乘法寄存器逐位乘法后计数器记录迭代次数；迭代实现乘法-移位-加法循环

二叉树乘法器

通过二叉树结构将串行各位加法变为二叉各位加法，将时间复杂度从 $\mathcal{O}(n^2)$ 降到 $\mathcal{O}(n\log_2 n)$

2位Booth编码与华莱士树型

Booth编码通过Abel变换，将整体计算复杂度减半

$-y_{31}\times 2^{31} + y_{30}\times 2^{30}+\cdots+ y_{0}\times 2^0 = (y_{29}+y_{30}-2y_{31})\times 2^{30}+\cdots+(y_0-2y_1)\times 1$

$f:(-y_{31},y_{30},\cdots, y_0)\to ((y_{29}+y_{30}-2y_{31}),\cdots,(y_0-2y_1))$

保留进位加法器CSA

CSA相比串行进位加法器的区别是，CSA不将下级进位Cin和本级进位Cout作为单独的输入/输出头，而是作为和加数/本位相加结果的输入/输出头。这个实现称为3-2压缩器

华莱士树

华莱士树基于CSA进行实现数位的3-2压缩树加法
wallace
华莱士树实现各级的伪和数组与进位数组的输出

超前进位加法器 CLA

CLA就是一块展开4级/8级迭代ALU的电路封装模块以优化加法过程。华莱士树输出伪和数组与进位数组后经由CLA进行加和得到最终的结果

浮点数的运算

算法计组