• 数据表示决定了计算机所执行操作的类型，数据从一个位置传到另一个位置的方法，
  以及对存储元件的特性要求。
• 浮点运算是非常重要的，因为它的实现决定了计算机执行复杂图形变换和图像处理的速度，
  而且浮点运算对计算的准确度也有很重要的影响。
• 计算机如何进行加减乘除运算

2.1 数据是什么

数据是 各种各样的信息，如数字、文本、计算机程序、音乐、图像、符号、运动图像、DNA密码，等等。
实际上，信息可以是能够被计算机存储和处理的任何事物。

2.1.1 位与字节

计算机内存储和处理信息的最小单位是位(bit，或比特)。一个比特的值可以是0或1，
它是 不可分的。

数字计算机将信息以 一组或一串比特 (称作 字)的形式保存在存储器中。
例如，串01011110表示一个8位的字。

计算机通过高低电压两个等级来存储0和1的状态

目前人们还不能制造出价格便宜的、能够可靠地区分出十个不同电压等级的电路，
只能制造出便宜的、能够区分我们称之为0和1的两个电压等级的电路。

计算机通常不会每次只对一个二进制位进行操作，它们会对一组二进制位进行操作。

• 8个二进制位为一个 字节 (byte)。

一般来讲，计算机能够 同时处理的位数越多，速度就会越快。
随着计算机的速度越来越快，价格越来越低，一台计算机一次能处理的位的组数也越来越多。

2.1.2 位模式

Figure :

上图描述了如何用1位、2位、3位和4位得到一个二进制的值序列。

一个n位的字将得到$2^n$条不同的路径或位模式。

信息表示

一个n位的字将得到$2^n$不同的位模式。

一个n位的二进制字什么也表示不了; 二进制1和0组成的串 没有任何内在含义。

怎样解释一个特定的二进制数只取决于程序员赋予它何种含

• 指令: 字长为32位或更长的计算机用一个字来表示cpu能够完成的操作。
  8位或16位计算机用多个字表示一条指令。其二进制编码与功能之间的关系由设计者决定
• 数量: 一个字或多个字都可以用来表示数量。
  
  数可被表示为多种格式(如BCD整数、无符号二进制整数、有符号二进制整数、二进制浮点数、
  整数复数、浮点复数、双精度整数，等等)。
• 字符: 字符是一个叫作“字母表”的集合中的元素。
• ISO 7位字符码或ASCII码(美国信息交换标准代码)是在计算机工业中应用
  得非常广泛的一种编码，

• Figure :
  • 用7位表示一个字符，一共可以表示 $2^7=128$ 个不同的字符。
  • 其中有96个字符是可打印字符。
  • 其余32个是不可打印的，用于完成回车、退格、换行等特殊功能。
• 因为计算机都是面向字节的，它通常可以通过在最高位前补0的方法将7位ASCII码
  转换为8位
  • ASCII码表的 列号作为编码的高3位，行号作为编码的低4位
    • 例如: 字符"Z"二进制编码为 101 1010
• • 扩展ASCII编码
    • 最高位为0: 表示标准ASCII码
    • 最高位是1: 表示新的字符
• 图像、声音和视觉: 数字计算机处理大量表示声音、静态图像和视频的数据。
  • 组成照片的基本单位是像素(picture element)，
    每个像素的大小可以是 8 位(单色)或 24 位(三基)。
  • 视频作为 一串静态图像 依次传输，每秒发送60次（60次/s)
  • 声音通过波形信号采样

2.2 数字

2.2.1 位置计数法

按照位置记数法，一个n位的整数N的形式表示:

• 这里$a_i (i=0,1....,n-1)$是与b的i次幂相乘的系数(此处b为基数)。

用小数点将整数部分和小数部分分开，可以对位置记数法进行扩展，使其能表示实数。

一个用基数b的位置记数法表示的数的值被定义为:.

在计算机主要关注下列四种数制

• 十进制位置记数法不能精确地表示所有小数
• 同样，二进制也不能精确地表示所有小数

2.3 二进制运算

二进制算术运算的规则与十进制基本相同; 唯一的区别在于，十进制算术运算以10为基数，
每位有10个数字，而二进制运算以2为基数，每位只有2个数字。

Figure :

两个位相加可能产生 进位 或 借位

二进制加法示例

二进制减法示例

• 小数减去大数时，用大数减去小数，结果取负

二进制乘法示例

表示范围、精度、准确性和误差

• 表示范围(Range): 一个数所能表示的最大值和最小值的差就是它的表示范围。MAX-MIN
• 精度(Precision): 数的精度是数据表示得有多好的衡量标准之一
• 准确度(Accuracy): 数的表示值与其的真实值之间的差
• 误差(Error): 误差 = 真实值 - 测量值

2.4 有符号数

负数可以用很多种不同的方式表示，但计算机设计者选择了3种方法

• 符号及值表示法
• 二进制补码表示法
• 移码表示法。

每种方法都有其各自的优点和缺点。

2.4.1 符号及值表示法

一个n位字可以表示从 $0～2^{n-1}$ 共 $2^n$ 个可能的值。
例如，一个8位的字可以表示 $0,1,2,\cdots,254,255$ 共256个数

如果要表示负数，一种方法是用它的 最高位表示符号。

• 符号位为 0表示正数
• 符号位为 1表示负数。

有符号数的值为: $(-1)^S \times M$

• S: 符号位的值
• M: 数值部分的值

Figure :

n位有符号的表示范围为 $-(2^{n-1}-1)$ 至 $+(2^{n-1}-1)$。

确定是0有两种表示方法；例如在8位有符号数中，0的表示：
$00000000=+0$ 以及 $10000000=-0$

2.4.2 二进制补码

补数概念

补数的定义: 是对于给定的进位制，相加后能使自然数a的位数增加1的最小的数

设 n 位 b 进制数 a，规定如下

b进制数a的关于基数的补数(b的补数): $b^n - a$

b进制数a的关于减基数的补数(b - 1的补数，简称减补数、侪补数): $b^n - a - 1$

在N进制下，求数a的补数的计算方式

对于N进制的自然数 $a=a_ra{r-1}a{r-2}\cdots a_1a_0$
规定 数b的各位 $b_i=(N+1)+a_i$为，称数b为 a关于 N+1 的补数

在十进制下 求数 2304671 的补数。

• 令N=9时，自然数 2304671 对应的补数为 7695328
• 当N=10时，自然数 2304671 对应的补数为 7695328+1=7695329

在二进制下，求1的补数只需简单地将0与1相互替换。求二补数(即补码)，只需要将1的补数加1

• 二进制的 101010110 对应的1的补数是 010101001。
• 二进制的 101010110 对应的2补数是 010101001 + 1 = 010101010。

微处理器使用二进制补码系统表示有符号整数，因为它可以将 减法运算 转换为对 减数的补数的加法运算。

例如：用7加上5的补数就可以完成运算7减去5。

一个数与它的补数之和是一个常数

在n位二进制算术中，数P的补数为Q且 $|P| + |Q| =2^n$

补码: 一个n位二进制数N的补码定义为 $2^n - N$；

当8位二进制数 $N=5=00000101$，
补码 $[N]_补=2^8-N=100000000-00000101=11111011$

首先，对于二进制数来说，只要定好了位长，
进行反码（1的补数）和补码（2的补数）
其实是一件很简单的事情。在纯二进制的表示下，
只有0和1，别无他物。0111(4位)的反码就是1000，
补码就是1001（反码加1）。所谓正负、符号这些人赋予的意义都不存在，
只有二进制数和这些简单操作

在计算机中表示负数，如果用最高位表示符号这种“原码”方式，
虽然有利于人的阅读，但 不利于其本身的计算。
所以系统内部就 把负数统一用“其对应正数的补码”来表示，
而正数自己不用改变。这样变换后，正数虽然形式上没有变，
但与原码相比，含义却变了，因为 符号位已经不再是符号位了，

此时的 正数和负数 都在一致的“补码编码空间”中。 。

由于原码空间到补码空间的转化，只需要对负数进行，正数是不用
发生任何变化

正数在计算机“补码编码空间”中的表示和原码一致。
但这绝 不等价于 “对正数进行补码运算，结果是其本身”。

下面来看计算机中补码的运算过程：首先我们将4个数 +5，
-5，+7和 -7 以补码形式表示

• +5 = 00000101
• -5 = 11111011
• +7 = 00000111
• -7 = 11111001

下面计算 7 - 5

结果为9位二进制数100000010。如果忽略最左边一位(也叫“进位位”)，
结果为00000010 = +2，这正是我们所希望看到的结果。

下面计算5 - 7

结果为11111110(进位位为0)。我们预期的结果为-2;
即$2^8 - 2=10000000-00000010 = 11111110$ 。
再一次得到了所需要的结果。

考虑n位二进制算术运算 $Z=X-Y$，我们用X加上Y的补数来完成这一运算。
Y的补码为 $2^n - Y$，则有 $Z=X+(2^n-Y)=2^n+(X-Y)$。

也就是说，我们得到了所需要的结果，X-Y，
以及位于最左边的一个并不需要的进位(即 $2^n$)，而这个 进位被丢弃了。

一个数连续两次求补码得到本身

补码的特点

补码是一个真正的互补系统，因为 $+X+(-X)=0$。

补码0被表示为00…0，是唯一的。

补码的 最高位为符号位。

• 符号位为0，则该数为正
• 符号位为1，则该数为负。

n位二进制补码数的表示范围为 $-2^{n-1} ~ 2^{n-1}-1$。
对于n=8，补码表示范围为-128～~127。共有$2^8=256$个不同的数

补码加法和减法使用同样的硬件完成，因为补码减法由被减数加上减数的补数实现。

运算溢出: 5位有符号二进制补码数的表示范围为 -16～+15

如果两个正数相加且结果大于15，会超出5位二进制补码的表示范围

如果两个负数相加且结果小于-16，也会超出5位二进制补码的表示范围

2.5 乘法简介

2.5.1 移位运算

先介绍 二进制补码数的算术移位运算

• 二进制补码左移一位等价于将该数乘2。
  • 十进制数39的二进制表示为00100111,
    左移一位得到01001110，对应于十进制数78。
  • 有符号二进制补码数11100011表示十进制数–29,
    左移一位之后的结果是11000110，表示十进制数-58。

• 二进制数右移一位相当于它除以2。
  • 00001100(十进制数12)右移一位得到00000110(十进制数6)。
    
    
    
    注意，00001101(即13)右移一位也会得到00000110，也是6;
    这是因为移出的 最低位被丢弃 了。
  • 为了在移位时保持二进制补码数的 符号不变，右移时应该复制符号位。
    
    
    考虑11100010(即-30), 右移一位同时保持符号位不变将得到11110001，
    等价于-15。

2.5.2 无符号二进制乘法

人们手动计算乘法过程

数字计算机并没有实现上面的算法，因为这种算法要求计算机存储n个部分积，
然后将它们同时相加。

一种更好的技术是每得到一个部分积时就做一次加法。

一个计算两个n位无符号二进制数相乘的算法。

算法示例

2.5.3 快速乘法

通过 移位和加法 实现的乘法速度很慢。实际的计算机采用了多种方法加快乘法运算的速度。
例如，构造专门的 逻辑阵列直接得到两个数的积 而不必对操作数移位。

与负数相乘

Figure :

使用移位和加法等速度相对较快的操作以避免使用乘法。考虑P乘以10和P乘以9

• $10P=2\times (2 \times 2 \times P + P)$: 即将P左移两次，加上P，再将和左移一次。
• $9P=2\times 2 \times 2 \times P + P$: 即将P左移三次,加上P得到结果。

借组查找表实现，将两个数相乘所有可能的积都保存在一个只读存储器内,
只需要进行简单查找表就可以确定乘积。

• 占用空间太大
• 减少查找表的大小
• 假设要计算两个16位数A与B的乘积。
• 可以将16位数A拆分为两个8位数$A_u$和$A_l$，
• 如果A=1111000010101010，则$A_u=11110000$，$A_l=10101010$。
• A可被表示为$A_u x 256 + A$, 同理B也可以这样表示

• Figure :

2.5.4 除法

二进制除法和十进制出发计算类似

计算机实现的除法算法--恢复余数除法

唯一需要修改的就是除数与部分被除数的比较方法。
人们用心算进行比较，而计算机必须做减法并检测结果的符号位。
如果减法的 结果为正，则商1，
但若 结果为负，则应商О 并将 部分被除数与除数相加，
将其 恢复为原先的值

Figure :

恢复余数除法示例

Figure :

计算机实现的除法算法--不恢复余数除法

部分被除数减去除数之后，将检测新的部分被除数的符号位。

• 若为 负，则商左移1位，商的最低位补0，并将部分被除数 加上 除数的二分之一。
• 若为 正 ，则商左移1位，商的最低位补1，并将部分被除数 减去 除数的二分之一。

Figure :

不恢复余数除法示例

2.6 浮点数

浮点数即为实数，称为浮点数的原因是小数点在数中 位置不固定。

浮点数存储分成 两部分：数值和小数点在数值中的位置

使用科学计数法来表示浮点数，科学计数法的好处是可以表示很大或者很小的数。

• 在十进制运算中，科学计数法表示的数字被写成 $尾数×10^{指数}$ 的形式，
• 二进制浮点数则被表示为 $尾数×2^{指数}$ 的形式。

其中 尾数表示值; 指数表示小数点在数值中的位置

计算机中浮点数运算结果 一般是不确定的。不同芯片对浮点数的出来可能是不同的。

由于浮点数被定义为两个值的积，浮点数的表示并不唯一，需要对其进行规格化。

规格化

为了使表示法的固定部分统一，科学计数法（用于十进制）和浮点表示法（用于二进制)
都在 小数点左边使用了唯一的非零数码，这称为 规范化 。
十进制系统中的数码可能是1～9，而二进制只能是1.

偏置指数(余码系统)：指数使用n位表示；给指数加上一个常熟，使得最小负指数为0

• 这个常数为: $2^{n-1} - 1$

下图给出了 4位指数 的偏置指数对应关系。

2.6.1 IEEE浮点数

IEEE 754浮点数标准提供了3种浮点数表示

• 32位单精度浮点数
• 64位双精度浮点数
• 128位四精度浮点数

一个32位IEEE 754单精度浮点数可以被表示为下面的二进制位串:
S EEEEEEEE 1.MMMMMMMMMMMMMMMMMMMMMMM

• S为符号位，指明这个数是正数还是负数
• E为8位偏置指数，指出了小数点的位置，表示尾数扩大或缩小 $2^E$倍
• M是23位小数尾数。
  • 尾数最前的那个1被省掉了

32位IEEE754浮点数结构

• S位为符号位，决定了数的符号。若S=0，该数为正数,若S=1，则该数为负。
• 指数E将浮点数的尾数扩大或缩小2的E次方倍,并且它的偏置值为127。
• 非零的IEEE 754标准的浮点数可表示为: $X=(-1)^S\times 2^{E-B}\times 1.F$
  • S: 符号位
  • E: 偏置值为B的指数
  • F: 尾数的小数部分(实际为1.F)

• 浮点数0表示为: $S=0 E=0 F=0000...000$

IEEE754浮点数格式

• 非数(Not a Number, NaN): 是IEEE 754标准的一个重要概念。
  NaN是IEEE 754标准提供的一个专门符号，
  代表IEEE 754标准格式所 不能表示的数。
  NaN 的使用和定义是与系统相关的,
  可以用NaN来表示所需要表达的任何信息。

Figure :

十进制转为二进制浮点数示例

二进制浮点数转为十进制数

浮点数的特点

接近0的浮点数: 指数为2位;；尾数为2位的浮点数系统

Figure :

浮点数0附近有一块 禁止区，其中的浮点数都是 非规格化的，
因此无法被表示为IEEE标准格式。这个数的指数和起始位都是0的区域，也可用来表示浮点数。
不过，这些数都是非规格化的，其 精度比规格化数的精度低，会导致 渐进式下溢。

IEEE标准的其他特点

• 缺省的舍入应该 向最近的值舍入。
  
  如果一个数与两个最近的可表示的值的 距离相等，则选择 最低位为0的作为舍入值;
  也就是说, 向偶数值舍入。
  
  标准要求必须提供(向0舍入,向正无穷大舍入,向负无穷大舍入)3种舍入模式。
   
• 规定了4种比较结果，分别是 等于、小于、大于 和 无序
  • 无序,用于一个操作数是NaN数的情形。

• 规定了5种异常。异常或中断是一种强制计算机进行专门处理机制。

IEEE标准定义的异常有:

• 操作数不合法——当程序员试图使用一些不合法的操作数
  (如 NaN 数，与无穷大数相加或相减时,或求负数的平方根)时,会引发这种异常。
  
   
• 除数为0——当除数为0(因为结果为无穷大)时,会引发这种异常。
   
• 上溢——当结果比最大浮点数还大时会引发这种异常。
  
  处理上溢的方法有 终止计算 或 饱和运算(用最大值作为结果)等。
  
   
• 下溢——当结果比最小浮点数还小时会引发这种异常;
• 结果不准确——当某个操作产生 舍入错误 时会引发这种异常。

2.7 浮点数运算

浮点数时不能直接进行加法运算。

浮点数加法的计算步骤: 先对阶数，尾数相加，结果规格化。

第1步，找出指数较小的那个数。
第2步，使两个数的指数相同。对于指数小的那个数，指数加几，就将尾数右移几位。
第3步，尾数相加(或相减)。
第4步，如果有必要，将结果规格化(后规格化)。

Figure :

因为 指数 有时与 尾数 位于同一个字中，在加法过程开始之前必须将它们分离开(解压缩)。

如果两个指数的差大于p+1，这里p为尾数的位数，较小的那个数由于太小而无法影响较大的数，
结果实际上就等于较大的那个数。

结果规格化时会检查指数，看它是否比最小指数小或比最大指数大，
以分别检测指数下溢或上溢。指数下溢会导致结果为0，
而指数上溢会造成错误，可能会要求操作系统介入处理。

舍入与截断误差

因为浮点运算可能引起尾数位数的增加，因此需要能够保持尾数位数不变的方法。
最简单的技术叫作截断(truncation)。

截断会产生 诱导误差(induced error)(即误差是由施加在数上的操作计算所引起的)，
诱导误差是偏置的，因为 截断后的数总是比截断前的小。

舍入(rounding)是一种更好的减少数的位数的技术。
如果丢弃的位的值 大于 剩余数 最低位 的一半，则将剩余数的最低位加1。

• 舍入更加精确并会引起 非偏置的误差。
• 截断总会使结果变小，带来系统性误差，
• 舍入的主要不足在于它需要对结果进行一个 额外的算术操作

舍入机制

• 最简单的舍入机制是截断或向0舍入。
• “向最近的数舍入”方法，会选择 距离该数最近 的那个浮点数作为结果。
• “向正或负无穷大舍入”方法，会选择 正或负无穷大方向上最近 的有效浮点数作为结果。

当要舍入的数位于两个连续浮点数的正中时，IEEE舍入机制会选择最低位为0的点(即向偶数舍入)。

2.8 浮点数与程序员

整数操作时精确、可重复的，浮点数操作是不精确的。

考虑表达式 $z = x^2-y^2$，x、y、z都是实数。
可以将表达式视作 $x^2-y^2$ 或 $(x+y)(x-y)$ 计算，整数运算得到相同结果，
但浮点数运算可能得到不同结果。

IEEE要求加、减、乘和除运算结果能够 精确计算，并用向偶数舍入的方法将结果舍入为最近的浮点数。

2.8.1 误差传播

舍入造成的生成误差(generated error)或通过计算链传播的传播误差(propagated error)
都会被引人浮点运算。

2.8.2 生成数学函数

考虑使用泰勒公式来求一些高级函数在某点的值。