2.数据的表示和运算

2.1数制与编码

2.1.1进位计数制及其相互转换

采用二进制的原因

二进制只有01两种状态，只用两个稳定状态的物理器件就可以表示二进制数的每一位。
二进制的0和1恰好与逻辑的真和假相对应。
二进制的编码和运算规则简单，能通过逻辑门电路便捷实现

进位计数法

在进位计数法中，每个数位所用的到的不同数码的个数被称为基数，十进制的基数为10（0-9），每个计数位满10向高位进位。数码的值等于每个数位上的数所表示的值乘以一个和它数位有关的常数，这个常数为位权，一个进位数的大小就是它的各位数码按权相加。

二进制：逢二进一，任意数位的权为$$2^i$$,i为所在我位数。
八进制：基数为8，逢八进一，三个二进制放在一起就组成一个八进制数。
十六进制：基数为16,有0-9，A-F，16个不同的数码，A-F分别表示10-15,，逢16进1，四个二进制放在一起就是1个十六进制数。

B一般表示二进制数，O表示八进制数，H表示十六进制数，也可用前缀0x表示十六进制数

不同进制数中间的相互转换

二进制数转换为八进制和十六进制：以小数点为分割线，八进制每三个一组，十六进制每四个一组，每组对应一个数。不够补零。
任意进制数转换为十进制：各位数码与各位权值想乘再想加。
十进制转换为任意进制：对整数部分用除基取余法，对小数部分用乘基取整法。

2.1.2定点数的编码表示

真值和机器数

真值：日常生活中，数一般由+，-组成，例如+5，-1等，这种带+，-的数被称为真值，为机器数所代表的实际值。

机器数：在计算机中，将+，-进行编码，通常0表示+，1表示-，这种把符号数字化的数称为机器数。常用的有原码、补码和反码表示法。

机器数的定点表示

根据小数点的位置是否固定，计算机中有两种数据格式：定点表示和浮点表示。在现代计算机中，一般选用补码整数表示整数，用原码小数表示浮点数的尾数部分，用移码表示浮点数的阶码部分。

定点表示法来表示定点小数和定点整数

定点小数：纯小数，规定其符号位在小数点之前，小数点在有效数值部分最高位之前。如X=x0,x1x2x3x4x5,其中x0为符号位，x1为有效数值部分最高位。
定点整数：小数点在有效数值最低位之后，第一位为符号位，如X=x0x1x2x3x4，其中，x0为符号位，x1—x4为有效数值。

注：在机器的内部并没有小数点，只是人为规定了小数点的位。

原码、补码、反码、移码

原码表示法

机器数的最高位表示符号位，其余各位表示数的绝对值。如果有n位，则原码的表示范围为$$-(2^n-1)到2^n-1$$。

原码表示的优点：
1. 原码与真值的对应关系简单，转换简单。
2. 用原码实现乘除运算比较简便。
原码表示的缺点：
1. 对于0的表示不唯一，有+0和-0两个编码。
2. 用原码实现加减运算比较复杂
补码表示法

补码的加减运算一律采用加法操作来实现。正数的补码和原码相同。在补码中，0的表示唯一，补码比原码的表示范围多1一个，即$$-2^n$$。

补码和真值的相互转换：

对于正数，与原码的方式一样，对于负数，符号位取1

变形补码：一种采用双符号位的补码表示，也称模4补码，
反码表示法（了解）：负数的补码可以用各位取反，末位加1的方法得到，若仅各位取反不加1，则为负数的反码表示，正数的反码的定义和相应的补码或原码相同。
移码表示法：常用来表示浮点数的阶码，它只能表示整数。

移码就是在真值X上加上一个常数（偏置值），这个数通常取$$2^n$$,相当于真值X在数轴上向正方向偏移了若干单位。

移码的特点：
1. 移码中0的表示唯一。
2. 一个真值的补码和移码仅差一个符号位，将补码的符号位取反就得到移码。
3. 移码全0时，对应真值的最小值$$-2^n$$,移码全1时，对应最大值$$2^n-1$$.
4. 移码保持了数据原有的大小顺序，移码大真值就大，移码小真值就小。

原码、补码、反码和移码这四种编码表示的总结：

原码、补码、反码的符号位相同，正数的机器码相同。
原码、反码的表示在数轴上对称，二者对0的表示都存在两种。
补码、移码的表示在数轴上不对称，零的表示唯一，它们比原码、补码多表示一个数。
整数的补码、移码的符号位相反，数值位相同。
负数的补码、反码末位相差1。
原码很容易判断大小。而负数的补码、反码很难直接判断大小。

判断方法：对于负数，数值位越大，其绝对值越大，即负的越多。

2.1.3 整数的表示

无符号整数的表示

定义：当一个编码的全部二进制均为数值位而没有符号位时，其为无符号数。此时默认符号为正，因此在相同位数下，无符号数能够比符号数表示的范围要大。

应用：来表示地址或者指针等。

有符号整数表示

原码、补码、反码、移码都能够表示有符号整数，但是补码表示有其明显的优势：

1.与原码和反码相比，补码对0的表示唯一。

2.与原码和移码相比，补码运算规则更简单，并且符号位可以和数值位一起参与运算。

3.与原码和反码相比，补码比原码和反码多表示一个最小负数。

2.1.4 C语言中的整数类型及类型转换

C语言中的整型数据类型

C语言中的整型数据就是定点整数，根据位数的不同，可分为char型（8位）、短整型（short 或short int， 16位）、整型（int 32位）、长整型（long 或 long int 在32为计算机中为32位，在64位计算机中为64位）。

特殊:char类型，其他类型如short/int/long 等在不指定signed/unsigned 时默认都是有符号整数，但char默认为无符号整数。（unsigned int/long/int）的全部二进制位都为数值位，相当于数的绝对值。

整型数据类型都是按照补码形式存储的，因此，unsigned全为数值位，表示的范围也有所不同。

有符号数和无符号数的转换

强制转换格式（C语言）：TYPE b=(TYPE)a，强制将a转换为TYPE 类型。

int main(){
    short x=-4321;
    unsigned short y=(unsigned short)x;
    printf("x=%d， y=%u\n",x,y);
}

有符号数x是一个负数，而无符号数y的表示范围不包括x的值

在采用补码的机器上，会导致输出以下结果：

x=-4321，y=61215.

x：1110111100011111

y：1110111100011111

观察可得，short强转为unsigned short型只改变了数值，但两个变量对应的每位都是一样的。强制类型转换的结果是保持位值不变，仅仅改变了这些位的方式

int main(){
    unsigned short x=65535;
    short y=(short)x;
    printf("x=%d， y=%u\n",x,y);
}

结果：

x=65535；y=-1；

将x从unsigned short型转换成short型，第一位数值变成了符号位，因此该y的值变成了-1；

注意：

C语言的标准里，若同时出现无符号数和有符号数进行运算，则一律按照无符号数运算。

不同字长整数之间的转换

int main(){
    int x=165537,u=-34991;
    short y=(short)x,v=(short)u;
    printf("x=%d， y=%d\n",x,y);
    printf("u=%d， v=%d\n",u,v);
}

结果：

x=165537,y=-31071

u=-34991,v=30545

在大字长变量向小字长变量强制转换时，系统会把多余的高位部分直接截断，低位部分直接赋值。

int main(){
    short x=-4321;
    int y=x;
    unsigned short u=(unsigned short)x;
    unsigned int v=u;
    printf("x=%d, y=%d\n",x,y);
    printf("u=%d, v=%d\n",u,v);
}

运行结果：

x=-4321，y=-4321；

u=61215，v=61215；

小字长到大字长的转换时，要使相应的位值相等，还要对高位部分进行扩展。如果原数字是无符号数，则进行零扩展，扩展后的高位用0填充，否则进行符号扩展，扩展后的高位部分用原数字的符号位填充。

注：char类型为无符号数，扩展后直接在高位补0即可。

2.2 运算方法和运算电路

2.2.1 基本运算部件

运算器：由ALU（算数逻辑单元 arithmetic logic unit）、移位器、状态寄存器和通用寄存器组成。

基本功能：包括加、减、乘、除四则运算，与、或、非、异或等逻辑运算，以及移位、求补等操作。 ALU的核心是加法器

带标志加法器

无符号数加法器只能用于两个无符号数的相加，不能进行有符号整数的加减运算。如果想进行有符号整数的运算，需要在无符号加法器的基础上增加相应的逻辑门电路，让加法器不仅能够计算和/差，还可以生成相应的标志信息。

算术逻辑单元（ALU）

ALU是一种功能较强的组合逻辑电路，能够进行多种算术运算和逻辑运算，因为加减乘除等运算最好都能转换成加法运算，所以ALU的核心是带标志加法器，同时也能执行“与“”或“”非“等逻辑运算。同时，ALU也可以实现左移或右移的移位操作。

2.2.2 定点数的移位运算

当计算机没有乘/除法运算电路时，可以通过加法和移位相结合的方法来实现，对于任意的一个二进制数来说，左移移位，如果不产生溢出的话，相当于乘2（十进制左移一位相当于乘10）;右移一位，不考虑因移出而舍去的末位尾数时，相当于除以2。

逻辑移位

逻辑移位时将操作数看作无符号整数。逻辑移位的规则：左移时，高位移出，低位补0；右移时，低位移出，高位补0.对于无符号整数的逻辑左移，如果高位的1移出，则发生溢出。

算数移位

算数移位需要考虑符号位的问题，将操作数看作有符号整数。由于计算机中的有符号整数都是采用补码表示的，对于有符号整数的移位操作应采用补码算术移位方式

补码算术移位：左移时，高位移出，低位补0；若左移后的数和原来的数的符号位不同，则发生溢出。右移时，低位移出，高位补符号位，若低位的1移出，则影响精度。如补码1001和0101左移会溢出，右移会丢失精度。

2.2.3 定点数的加减运算

补码的加减法运算

补码运算的特点：

按二进制运算规则运算，逢二进一。
若做加法，两个数的补码直接相加，则被减数的与减数的负数补码相加。
符号位和数值位一起参与运算，加、减运算结果的符号位也在运算中直接得出。
最终的运算结果的高位丢弃，保留n+1位，运算结果仍然为补码。

溢出判别方法

仅当两个符号相同的数相加或两个符号不同的数相减才会发生溢出。如两个正数相加，而结果的符号位却为1；一个负数减去一个正数，结果的符号位却为0。

补码定点数加减运算溢出的判断方法：

采用一位符号位，只要参加操作的两个数的符号相同，而结果又与原操作数的符号不同，则表示结果溢出。
采用双符号位，运算结果的两位符号位s1，s2相同，则表示未溢出，运算结果的两个符号位s1，s2不同则表示溢出，此时最高位符号位代表真正的符号。
采用一位符号位根据数值位的进位情况来判断溢出，若符号位的进位与最高数的进位相同，则表示无溢出，否则说明有溢出。

各种标志

1.零标志ZF：ZF=1表示运算的结果为0，对于无符号位和有符号位的运算，ZF都有意义。

2.溢出标志OF：判断有符号数的运算结果是否溢出，它是符号位进位和最高数位进位的异或结果。OF=Cn⊕Cn-1,对于无符号数的运算，OF没有意义，它无法判断无符号数运算是否溢出。

3.符号标志SF：表示结果的符号，即结果的最高位，对于无符号位运算，SF没有意义。

4.进位/错位标志CF：表示无符号数运算时的进位/借位，判断是否发生溢出。加法时CF=1，表示结果溢出，因此CF等于进位输出Cout，减法时，CF=1表示有借位，不够减，CF等于进位输出Cout取反。综合可得CF=Sub⊕Cout,对于有符号数来说，CF没有意义。CF无法判断有符号数是否溢出。

无符号数比较大小：1.A-B=0，ZF=1,CF=0,（ZF代表结果为0，CF表示无借位）。

2.A<B，ZF=0,CF=1.(代表结果不为0，有进位，不够减)。

3.A>B, ZF=0,CF=0.(代表结果不为0，且没有借位)。

有符号数比较大小：对于有符号数，零标志ZF,溢出标志OF，符号标志SF才有意义。

设有两个有符号数，A,B用补码表示。A-B为例

若A=B 结果ZF=1,SF=0,OF=0,

若A>B A-B=010-001 = 010+111 =001，此时ZF=0,SF=0,OF=0;

A-B=011-101 = 011+011=110, 此时ZF-0,SF=1,OF=1;

若A<B A-B=000-001=000+111=111, 此时ZF=0,SF=1,OF=0;

A-B=101-011=101+101=010,此时ZF=0,SF=0,OF=1;

2.2.4 定点数的乘除运算

定点乘法运算

原码乘法的特点是符号位与数值位是分开求的，分为两步，第一步乘积的符号位由两个乘数的符号位通过异或操作得到，乘积的数值位是两个乘数的绝对值之积。详细手算过程。补码一位乘法。

定点除法运算

除法运算的过程：1.被除数与除数相减，够减则上商为1，不够减则上商为0。

2.每次得到的差为中间余数，将除数右移与上次的中间余数比较，用中间余数减余数，够减则上商1，不够则上商0，如此重复，直到商的位数满足要求。

2.3 浮点数的表示与运算

2.3.1 浮点数的表示

浮点数指以适当的形式将比例因子表示在数据中，让小数点的位置根据需要而浮动。这样，在位数有限的情况下，既扩大了数的表示范围，又保持了数的有效精度。

浮点数的表示格式

通常，浮点数的表示格式为：$$ N=(-1)^S×M×R^E$$

其中，S取值0或1，用来决定浮点数的符号；M是一个二进制小数，称为尾数，一般用定点原码小数表示，E是一个二进制定点整数，称为阶码或指数，用移码表示。R是基数（隐含）可以约定为2、4、16等。由此可见浮点数由符号、尾数和阶码这三部分组成。阶码的位数反映浮点数的表示范围，尾数的位数反映浮点数的精度。

浮点数的表示范围

因为原码的表示范围是关于原点对称的，所以，浮点数的范围也是关于原点对称的。若运算的结果大于最大正数时称为正上溢，小于绝对值最大负数时称为负上溢，正上溢和负上溢统称为上溢,数据一旦溢出，计算机必须进行溢出处理。当运算结果在0至最小正数之间称为正下溢，在0至绝对值最小负数之间时称为负下溢。正下溢和负下溢统称为下溢。在发生下溢时，浮点数值趋于0，计算机将其当做机器零处理。

浮点数的规格化

让浮点数在运算过程中尽可能多一点保留有效数字的位数，让有效数字尽量占满尾数数位，必须在运算过程中对浮点数进行规格化操作。规格化操作：通过调整一个非规格化浮点数的尾数和阶码的大小，使其在尾数的最高数位上保证是一个有效值。

左规：当运算结果的尾数的最高数位不是有效位时，需要进行左规，左规时，尾数每左移一位，阶码减1（基数为2时）。左规可能要进行多次

右规：当运算结果的尾数的有效位进到小数点的前面时，需要进行右规，右规只需要进行一次。将尾数右移一位，阶码加1（基数为2时）。右规时，阶码的增加可能会导致溢出。

IEEE754标准

IEEE754标准规定常用的浮点数格式有32位单精度浮点数（短浮点数，float型）和64位双精度浮点数（长浮点数、double型），其基数隐含为2。

单精度格式包含1位符号位s、8位阶码e和23位尾数f；

双精度格式包含1位符号位s，11位阶码e和52位尾数f。

基数隐含为2，尾数用原码表示。对于规格化的二进制浮点数，尾数的最高位总是1，为了能使尾数多表示一位数位，将这个1给隐藏，称为“隐藏位”，因此23位尾数实际表示了24位有效数字。IEEE754标准规定隐藏位1的位置在小数点之前。

在IEEE754标准中，指数用移码表示，但这个移码不是通常n位移码所用的$$2^{n-1}$$,而是$$2^{n-1}-1$$,因此，单精度和双精度浮点数的偏置值分别为127和1023。在存储浮点数阶码之前，偏置值要先加上真值，移码等于偏置值加真值。

阶码和尾数为零的意义：

全0阶码全0尾数：+0/-0，零的符号取决于符号s，一般情况下+0和-0是等价的。
全1阶码全0尾数：:+∞/-∞。+∞在数值上打渔所有的有限数，-∞小于所有的有限数。引入其的目的是当计算过程出现异常的时候程序也能继续运行下去。
全1阶码非0尾数：NaN（not a number）。表示一个没有定义的数，称为非数。
全0阶码非0尾数：非规格化数。阶码全为0，尾数不全为0.非规格化数的隐藏位为0，且单精度和双精度浮点数的指数分别为-126和-1022。非规格化数可以用来处理阶码下溢。

定点、浮点表示的区别

数值的表示范围：若定点数和浮点数的字长相同，则浮点数表示法能够表示的数值范围远大于定点数。
精度：对于字长相同的定点数和浮点数来说，浮点数虽然扩大了表示范围，但精度却降低了。
数的运算：浮点数包括阶码和尾数两个部分，运算时不仅要做尾数的运算，还要做阶码的运算，而且运算结果要求规格化，所以浮点运算比定点运算复杂。
溢出问题：在定点运算中，当运算结果超出数的表示范围时，发生溢出；在浮点运算中，运算结果超出尾数表示范围却不一定溢出，只有规格化后阶码超出所能表示的范围才发生溢出。

2.3.2 浮点数的加减运算

对阶

使两个操作数的小数点位置对齐，使两个数的阶码相等。先求阶码差，然后以小阶向大阶对齐的原则，将阶码小的操作数的尾数向右移一位，阶码加1，直到和大的操作数的阶码相同。尾数右移时，若舍弃有效位会产生误差，影响精度。为保证运算的精度，尾数右移时，低位移出的位不要丢掉，应保留并参加尾数部分的运算。

尾数加减

将对阶后的尾数按定点原码小数的加减运算规则进行运算。因为IEEE754标准中浮点数尾数中还有一个隐藏位，因此需要将隐藏位还原到尾数部分再进行计算。计算后的尾数不一定是规格化的，因此，浮点数的加减运算需要进一步进行规格化。

右规：当结果为1X.XXXXXXXXX时需要进行右规。尾数右移1位，阶码加1，最高位1移到小数点前一位作为隐藏位，最后一位移出时，需要考虑舍入。

左规：当结果为0.0000001时，需要进行左规，尾数左移一位，阶码减1，直到1移到小数点左边。

舍入

在对阶和尾数右规时，可能会对尾数进行右移，一般将移出的部分低位保存下来，参加中间过程的运算，直到最后再将运算结果进行舍入，还原表示成IEEE754格式。

IEEE754有四种舍入形式：

就近舍入：舍入为最近的可表示数。
正向舍入：朝数轴+∞方向舍入，取右边最近的可表示数。
负向舍入：朝数轴-∞方向舍入，取左边最近的可表示数。
截断法：直接截取所需位数，丢弃后面的所有位。

溢出判断

在尾数规格化和尾数舍入时，可能会对结果的阶码执行加/减运算。因此，必须考虑指数溢出问题。若一个正指数超过了最大允许值（127或1023），则发生指数上溢，产生异常。若一个负指数超过了最小允许值（-149或-1074），则发生指数下溢，通常把结果按机器零处理。

2.3.3 C语言中的浮点数类型

C语言中的float型和double型分别对应于IEEE754单精度浮点数和双精度浮点数。

int型转换成float型时，虽然不会发生溢出，但float型尾数连隐藏位共24位，当int 型数的第24—31位非0时，无法精确转换乘24位浮点数的尾数，需舍入处理，影响精度。
int型或float型转换为double型时，因double型的有效位数更多，因此能保留精确值。
double型转换成float型时，因float型的表示范围更小，因此大数转换时可能会发生溢出。此外，由于尾数的有效位变少，因此高精度数转换时会发生舍入。
float型或double型转换为int型时，因为int型没有小数部分，因此数据会向0方向进行截断，只保留整数部分，发生舍入。int型的表示范围更小，因此大数转换时可能会溢出。

2.3.4 数据的大小端和对齐存储

数据的“大端方式”和“小端方式”存储

在存储数据时，数据从低位到高位可以从左到右排列，也可以按从右到左排列。因此，无法用最左或最右来表征数据的最高位或最低位。通常用最低有效字节（LSB）和最高有效字节（MSB）来分别表示数据的低位和高位。例如，一个int型变量i的机器数为01 23 45 67H，最高有效字节MSB=01H，最低有效字节LSB=67H。

现在计算机基本采用字节编址，即每个地址编号中存放1字节。int和float型占4字节，double型占8字节。程序对每个数据只给定一个地址。假设变量i的地址为0800H，字节01H、23H、45H、67H各有一个内存地址。有两种排列方式：

0800H 0801H 0802H 0803H

大端方式：01H 23H 45H 67H
小端方式：67H 45H 23H 01H

大端方式：先存储高位字节，后存储低位字节。字节中的顺序和原序列的相同。

小端方式：先存储低位字节，后存储高位字节。字节中的顺序和原序列的相反。