数据的表示和运算
一、数值和编码
1.基本概念
①进位制：表示数时，仅用一位数码往往不够用，必须用进位计数的方法组成多位数码。多位数码每一位的构成以及从低位到高位的进位规则称为进位计数制，简称进位制。
②数值数据：可用来表示数量的多少，可比较其大小，分为整数和实数，整数又分为无符号整数和带符号整数。
③非数值数据：没有大小之分，不表示数量的多少，主要包括字符数据和逻辑数据。
2.进位记数制
数值型数据（如±99.625）的完整表示必须解决如下三个问题：
1.99.625如何表示：采用什么进位计数制
2.符号（±）如何表示：机器数的编码方法
3.小数点如何表示：定点表示或浮点表示
①十进制数
特点：
- 符号为：0~9；基数是10
- 运算规律：逢十进一，即：9+1=10
基数：进制位的基数，就是在该进制位中可能用到的符号个数。
位权（位的权数）：在某一进位制的数中，每一位的大小都对应着该位上的数码乘上一个固定的数，这个固定的数就是这一位的权数。权数是一个幂。如十进制数第i位上的权位10。
②二进制数
特点：
符号为：0、1；基数是2。
运算规律：逢二进一，即：1+1=10.
二进制数的权展开式：
二进制运算规则：
加法规则：0+0=0, 0+1=1, 1+0=1, 1+1=10
乘法规则：0.0=0, 0.1=0, 1.0=0, 1.1=1
结论：在计算机内部，所有信息都用二进制数字表示。
因为：
1.二进制只有两种基本状态，而使用有两个稳定状态的物理器件可以容易地表示二进制数的每一位；
2.二进制的编码、计数和运算规则都很简单，可用开关电路实现，简便易行；
3.两个符号“1”和“0”正好与逻辑命题的两个值“真”和“假”相对应，为计算机中实现逻辑运算和程序中的逻辑判断提供了便利的条件，特别是能通过逻辑门路方便的实现算术运算。
③八进制数
特点：0~7；基数是8。
运算规律：逢八进一，即7+1=10。
八进制数的权展开式：
④十六进制数
特点：
符号为：09、AF；基数是16。
运算规律：逢十六进一，即F+1=10。
十六进制数的权展开式：
总结：
各种进位计数制的标识方法：
3.不同进位记数制之间的转换
①R进制数转换成十进制数
任何一个R进制数转换为十进制数时，只要“按权展开”即可。
②十进制数转成R进制数
任何一个十进制数转成R进制数时，要将整数和小数部分分别进行转换。
1.整数部分的转换：
整数部分的转换方法是“除基取余，上右下左”。
也就是说，用要转换的十进制整数去除以基数R，将得到的余数作为结果数据中的各位的数字，直到余数为0为止。上面的余数（先得到的余数）作为右边低位上的数位，下面的余数作为左边高位上的数位。
2.小数部分的转换
小数部分的转换方法是“乘基取整，上左下右”。
也就是说，用要转换的十进制小数去乘以基数R，将得到的乘积的整数部分作为结果数据中各位的数字，小数部分继续与R相乘。以此类推，直到某一步乘积的小数部分为0或已得到希望的位数为止。最后，将上面的整数部分作为左边高位上的数位，下面的整数部分作为右边低位上的数位。
3.含整数、小数部分的数的转换
只要将整数部分和小数部分分别进行转换，得到转换后相应的整数和小数部分，然后再将这两部分组合起来得到一个完整的数。
③二、八、十六进制的相互转换
1.八进制数和二进制数之间的互换
二进制转为八进制：将二进制数由小数点开始，整数部分向左，小数部分向右，每3位分成一组，不够3位补零，则每组进制数便是一位八进制数。
（每组按照二进制转十进制的方法）
八进制转为二进制：将每位八进制数用3位二进制数表示。
（每一位数字按照十进制转二进制）
67-->110111
过程：6-->110 7-->111
2.十六进制和二进制之间的互换
二进制转十六进制：将二进制数由小数点开始，整数部分向左，小数部分向右，每4位分成一组，不够4位补零，则每组二进制数便是一位十六进制数。
十六进制转二进制：将每位十六进制数用4位二进制数表示。
（每一位数字按照十进制转二进制的方法）
4.定点数的编码表示
机器数：数值数据在计算机内部编码的表示。
真值；机器数真正的值（即现实世界中带有正负号的数）
机器数一定是一个0/1序列，通常缩写成十六进制形式。
前面的符号：0代表正，1代表负。
①原码表示法
一个数的原码表示由符号位直接跟数值位构成，因此，也称“符号-数值（sign and magnitude）”表示法。原码表示法中，正数和负数的编码表示仅符号位不同，数值部分完全相同。
原码编码规则如下：
原码的性质：
②补码表示法
1.模运算
说明：
（1）溢出：在两个同号数相加或异号数相减时，当运算结果超出了n位数可表示的范围时，则称为此时发生了“溢出（overflow）”现象。
（2）模运算：在两个同号数相减或两个异号数相加时，将运算结果超过n位时，将第n+1位舍去不影响其运算结果。舍去高位的操作相当于“将一个多于n位的数除以2n，保留其余数作为结果”的操作，也就是“模运算”操作。
2.补码的定义
根据上述同余概念和数的互补关系，可引出补码表示方法：
“正数的补码是它本身；负数的补码等于模与该负数绝对值之差。”
因此，数XT的补码可用如下公式表示。
③求负数补码的方法
方法一：变反加1法，即符号位不变，其余位变反，末低位加1。
方法二：搜索法：
从右往左搜索，遇到不同的就停下来，符号位保持不变，其余未被搜索的位取反（不包括遇到的那位不同的）。
④补码的性质
⑤由补码求原码与真值
⑥3.反码表示法
负数的补码可采用“各位求反，末尾加1”的方法得到，如果仅各位求反而末尾不加1，那么就可得到负数的反码表示，因此负数反码的定义就是在相应的补码表示中再末尾减1。
注意：原码运算符号位和数值位要分开处理，补码则一起处理。
⑦移码的定义
移码的性质：
二、整数的表示
1.无符号整数的表示
定点数：小数点的位置是固定的。
浮点数：小数点的位置根据需要可以左右移动。
定点整数：整数的小数点隐含在数的最右边，不需要表示小数点。
定点小数：整数的小数点隐含在最高数位的左边，不需表示小数点。
二进制整数分为：
①无符号整数（unsigned integer）：一个编码的所有二进制位都用来表示数值而没有符号位时。
2.带符号整数
②带符号整数（signed integer）：它必须用一个二进制位来表示符号，也被称为有符号整数。
带符号整数用补码表示，主要优点体现在以下方面
（1）与原码和反码相比，数0的补码表示形式唯一。
（2）与原码和移码相比，补码运算系统是一种模运算系统，因而可用加法实现减法运算，且符号位可以和数值位一起参加运算。
（3）与原码和反码相比，他比原码和反码多表示一个最小负数。
（4）与反码相比，不需要通过循环进位来调整结果。
3.C语言中的整数类型
无符号整数在C语言中对应unsigned short、unsigned int（unsigned）、unsigned long等类型，常在数的后面加一个“u”或“U”来表示，例如，12345U，0x2B3Cu等。
带符号整数在C语言里对应short、int、long等类型。C语言中允许无符号整数和带符号整数之间的转换，转换后数的真值是将原二进制机器数按转换后的数据类型重新解释得到。
三、实数的表示
1.浮点数的表示格式
计算机中专门用浮点数来表示实数
浮点数的格式：
2.浮点数的规格化
为了浮点数表示的唯一性和提高精确度，需要将非规格化的数转为规格化。
规格化：规定尾数的最高位必须是一个有效值。
规格化操作有两种：“左规” 和 “右规”。
右规：1.1010*2^3-->0.11010*2^4
左规：0.0101*2^3-->0.101*2^2
3.IEEE 754浮点数标准
①IEEE 754标准基本格式
提供了两种基本浮点数格式：32位单精度和64位双精度格式：
符号：S （正数为0，负数为1）
阶码：E （基数的指数）（单精度浮点数格式，阶码e=127+阶，双精度浮点数格式，阶码e=1023+阶）
尾数：M（小数部分，不够位数补0）
②说明：
- 基数隐含为2
- 尾数用原码表示，第一位总为1，因而可在尾数中缺省第一位的1，称为隐藏位，使得单精度格式的23位尾数实际上表示了24位有效数字，双精度格式的52位尾数实际上表示了53位有效数字。
- 阶用移码表示，偏置常数并不是通常n位移码所用的2n-1，而是（2n-1-1），因此，单精度和双精度浮点数的偏置常数分别为127和1023。
即，对于单精度浮点数格式，阶码e=127+阶，因此阶=e-127；
对于双精度浮点数格式，阶码e=1023+阶，因此阶=e-1023。 - 阶码e的范围：对于单精度浮点数格式，阶码e的范围为00000000 ~ 11111111，正常的规格化非0的数的阶码范围为00000001 ~ 11111110，
对应的最小阶为00000001-127=-126，
最大阶为11111110-127=254-127=127，
因此，对应的阶的范围为-126~127。
注意：IEEE 754规定隐藏位"1"的位置在小数点之前。
③IEEE 754标准格式中的特殊位序列P56表2.3
形成IEEE 754浮点数步骤：
①规格化二进制数：改变阶码，使小数点前面仅有第一位有效数字（1）；
②计算阶码：利用偏值表示法，实际指数加上偏移值。
③单精度浮点数的阶码加上偏移量7FH（127）；
④双精度浮点数的阶码加上偏移量3FFH（1023）；
⑤把数值的符号位、阶码和尾数组合在一起就得到了该数的浮点存储形式。
规格化总结：
有效位总要为1，
IEEE754的有效位在小数点前一位，
普通的浮点数有效位在小数点后一位
小数点第一位要隐藏。所以要左规
符号：S （基数的指数）
阶码：E （基数的指数）（单精度浮点数格式，阶码e=127+阶，双精度浮点数格式，阶码e=1023+阶）
尾数：M（小数部分，不够位数补0）
1100,0000,1010,0000,0000,0000,0000,0000
最高位是符号位 S：为1
去掉符号位1位，去掉阶码为8位，剩下的为尾数：010 0000 0000 0000 0000 0000 所以尾数小数部分f=0.01 转为十进制：0.25
阶码：中间的8位：100 0000 1 转为十进制：129
阶：e-127=129-127=2
4.C语言中的浮点数类型
当在int、float和double等类型数据之间进行强制类型转换时，程序将得到以下数值转换结果（假定int为32位）
①从int转换位float时，不会发生溢出，但可能有有效数字被舍入。
②从int或float转换为double时，因为double的有效位数更多，故能保留精确值。
③从double转换为float时，因为float表示范围更小，故可能发生溢出，此外，由于有效位数变少，故可能被舍入。
④从float或double转换为int时，因为int没有小数部分，所以数据可能会向0方向被截断。例如，1.9999被转换为1，-1.9999被转换为-1。此外，因为int的标识范围更小，故可能发生溢出。将大的浮点数转换为整数可能会导致程序出错，这是历史上曾经有过惨痛的教训。
四、非数值数据的编码表示
1.逻辑值
1.逻辑数据只能参加逻辑运算，并且使按位进行的，如按位“与”、按位“或”、逻辑左移、逻辑右移等。
2.逻辑数据和数值数据都是一串0/1序列，在形式上无任何差异，需要通过指令的操作码类型来识别它们。
2.西文字符
1.西文：由拉丁字母、数字、标点符号及一些特殊符号所组成，它们统称为“字符”（character）。
2.“字符集”：所有字符的集合。
3.码表：字符集中每一个字符都有一个代码（即二进制编码的0/1序列），构成了该字符集的代码表，简称码表。
4.ASCII码（美国标准信息交换码）：
ASCII字符编码有以下两个规律：
①字符09这10个数字字符的高三位编码为011，低四位分别为00001001
②英文字母字符的编码值也满足正常的字母排序关系，而且大、小写字母的编码之间有简单的对应关系，差别仅在b5这一位上，若这一位为0，则是大写字母；若为1，则是小写字母。
如大写字母A和B对应的ASCII值分别为41H和42H，小写字母a和b对应的ASCII值分别为61H和62H，A+20H=a，a-20H=A。
3.汉字字符
1.汉字的输入码
使每个汉字用一个或几个键来表示，这种对每个汉字用相应的按键进行的编码表示就称为汉字的“输入码”，又称外码。
2.字符集与汉字内码
在系统中进行存储、查找、传送等处理的一种编码形式。
①国际码（国际交换码）：1981年我国颁布了《信息交换用汉字字符编码字符集·基本集》（GB2312-80）。该标准为任意一个字符（包括汉字和其他字符）规定了一个唯一的二进制代码。
②UCS-4或UCS-2：国际标准ISO/IEC 10646提出了一种包括全世界现代书面语言文字所使用的所有字符的标准编码，每个字符用4个字节（称为UCS-4）或两个字节（称为UCS-2）来编码。
③UCS-2：我国（包括香港、台湾地区）与日本、韩国联合制订了一个统一的汉字字符集（CJK编码），共收集了上述不同国家和地区的共约2万多汉字及字符，采用2字节（即UCS-2）编码。
④Unicode：美国微软公司在Windows操作系统（中文版）中也已采用了中西文统一编码，其中收集了中、日、韩三国常用的约2万汉字，称为“Unicode”（2字节编码），它与ISO/IEC 10646的UCS-2编码一致。
3.汉字的字模点阵码和轮廓描述
汉字的字形主要有两种描述方法：
字模点阵描述和轮廓描述
①字模点阵描述是将字库中的各个汉字或其他字符的字形（即字模），用一个其元素由“0”和“1”组成的方阵（如1616、2424、32*32甚至更大）来表示，汉字或字符中有黑点的地方用“1”表示，空白处用“0”表示，我们把这种用来描述汉字字模的二进制点阵数据称为汉字的字模点阵码。
②汉字的轮廓描述方法比较复杂，它把汉字笔画的轮廓用一组直线和曲线来勾画，记下每一直线和曲线的数学描述公式。目前已有两类国际标准：Adobe Type1和Ture Type。这种用轮廓线描述字形的方式精度高，字形大小可以任意变化。
五、数据的宽度和存储
1.数据的宽度和单位
比特（bit）：进制数据的每一位（0或1）是组成二进制信息的最小单位，称为一个“比特”（bit），或称“位元”，简称“位”。比特是计算机中处理、存储和传输信息的最小单位。
字节（byte）：一个字节等于8个比特。在计算机内部，二进制信息的计量单位是“字节”（byte）。
字（word）：用来表示被处理信息的单位，用来度量各种数据类型的宽度。
注意：“字”和“字长”的概念不同。
“字”用来表示被处理信息的单位，用来度量各种数据类型的宽度。
“字长”通常指CPU内部用于整数运算的数据通路的宽度。
例如，Intelx86微处理器中把一个字定义为16位，但是，从80386微处理器开始，字长就至少是32位了。因此，即使在一个字长为32位的计算机中，32位也被称为双字宽。
2^8=256 （8bit=1byte）
2^10=1024 （1K=1024）
2^20=1048576 （1M=1048576）
2.数据的存储和排列顺序
大端（big endian）方式：高位（最左边是最高位）放在最小的地址单元中
将数据的最高有效字节MSB存放在最小地址单元中，
将最低有效字节LSB存放在最大地址单元中。
IBM 360/370，Motorola 68k，MIPS，Sparc，HP PA等机器都采用大端方式。
小端（little endian）方式：高位放在高地址中
将数据的最高有效字节MSB存放在高地址中，
将最低有效字节LSB存放在低地址中。
Intel 80*86，DEC VAX等都采用小端方式。
六、数据校验码
1.奇偶校验码
1.原理：（使1的个数为奇数或偶数，加1/0）
在k位信息码中增加1位校验位代码，使k+1位码字中取值为1的个数总保持为偶数（偶校验）或奇数（奇校验）。
2.形成校验码位的规则：
3.奇偶校验码的校验规则：
4.判断数据在传送中是否发生了错误（只能查出奇数个错，查不出偶数个错）
2.海明校验
1.主要思想：
将数据按某种规律分成若干组，对每组进行相应的奇偶检测，以提供多位校验信息，从而可对错误位置进行定位，并将其纠正。
2.编码过程
①确定校验位的位数
假定被校验数据M的位数为n，校验位P为k位，则n和k必须满足下列关系：
②确定分组方式
数据位和校验位是一起被存储的，通过将它们中的各位按某种方式排列为一个（n+k）位的码字，将该码字中每一位的出错位置与故障字的数值建立关系，这样就可通过故障字的值很快确定该码字中的哪一位发生了错误，从而将其取反来进行纠正。
3.故障字的值（字的每一位代表每一组的校验结果）
①如果故障字各位全部是0，则表示没有发生错误。
②如果故障字中有且仅有一位为1，则表示校验位中有一位出错，不需要纠正。
③如果故障字中多位为1，则表示有一个数据位出错了，其在码字中的出错位置由故障字的数值来确定。纠正时只要将出错位置取反即可。
4.类型
单纠错码（SEC）（能发现一位错，纠正一位错）
单纠错/双检错码（SEC-DED）（能发现两位，但只能改正一位）
3.循环冗余校验
循环冗余校验码（Cyclic Redundancy Check），简称CRC码，是一种具有较强检错、纠错能力的校验码，常用于外存储器的校验，在计算机通信中，也被广泛采用。
1.编码过程
假设要进行校验的数据信息M(x)为一个n位的二进制数据，生成多项式G(x)是一个k+1位的二进制数，则CRC编码过程为：
2.CRC码的校验方法
CRC码传送到接收方后，接收方用CRC码除以生成多项式来校验，
余数为0，传送正确；
余数不为0，传送出错。
多项式：10011（看x系数）
有错，因为1001010111101除以生成的多项式为：
七、加法器和算术逻辑部件
1.全加器和加法器
（1）全加器（Full Adder，简称FA）：同时考虑两个加数和低位进位的一位加法器。
①真值表：
②全加器的逻辑表达式：
③全加器符号
（2）加法器（无符号数加法器）：n位加法器可由n个全加器实现，其中Ci是第i-1位向第i位的进位。
2.带标志加法器
n位无符号数加法器只能用于两个n位二进制数相加，不能进行无符号整数的减运算，也不能进行带符号整数的加/减运算。要能够进行无符号整数的加/减运算和带符号整数的加/减运算，还需要在无符号数加法器的基础上增加相应的逻辑门路，使得加法器不仅能计算和/差，还要能够生成相应的标志信息。
补码加减运算表达式为：
总结：
由[x]原 求 [x]补：
x>0, [x]原=[x]补
x<0,[x]原--->[x]补:符号位不变，其余变反，末位加1
由[x]补求[-x]补：（不管x正负）
[x]补--->[-x]补:连同符号位一起变反，末位加1
求负数补码的另一种方法：
先写出该负数的相反数（正数），再将该正数的二进制形式写出来，
然后对这个二进制位串按位取反，即若是1则改为0，若是0则改为1，
最后在末位加1。
3.补码加减运算器
区分带符号整数运算结果和无符号整数运算结果：
①零标志ZF=1表示结果F为0。
②符号标志SF表示结果的符号，即F的最高位。对于无符号数运算，SF没有意义。
③进/借位CF表示无符号数加/减运算时的进位/借位。
加法时，若CF=1表示无符号数加法溢出；
减法时，若CF=1表示有借位，即不够减。
因此，加法时CF就应等于进位输出Cout；
减法时，就应将进位输出Cout取反来作为借位标志。
综合起来，可得：
例：
[-7-6]补=[-7]补+[-6]补
-7原码=1111
-6原码=1110
[1111]原=[1001]补
[1110]原=[1010]补
原式=[1001]补+[1010]补
=0011（+3）
[-3-5]补=[-3]补+[-5]补=1101+1011=11000=1000
注意：补码运算是一起运算的，不需要分开数值位和符号位，数值位进位到符号位，符号位若产生溢出，则舍去。
总结：当最高有效位有进位而符号位无进位时，产生上溢；
当最高有效位无进位而符号位有进位时，产生下溢；
（简单地说是正数相加为负数或负数相加为正数则产生溢出）
溢出判别方法：
①若符号位产生的进位Cn与最高数值位向符号位的进位Cn-1不同，则产生溢出，即：
②若两个加数的符号位Xn-1和Yn-1相同，且与和的符号位Fn-1不同，则产生溢出，即：
Cn：符号位向高位的进位
圈+符号：异或运算
例：符号位相加为0，Cn=0
最高位相加为1，Cn-1=1
0和1异或为1，所以发生了溢出。
两个正数相加为负数或者两个负数相加为正数都表示溢出了。
补码运算溢出的处理规则：
两个用补码表示的数相加时，如果最高位（符号位）有进位，则进位被舍弃。
4.算术逻辑部件
算术逻辑部件ALU是一种能够进行多种算术运算和逻辑运算的组合逻辑电路，其核心部件是带标志加法器，多采用先行进位方式。其符号入如下：
八、定点乘法运算
1.原码乘法运算（符号位和数值位分开处理）
原码乘法运算步骤：
①确定乘积的符号位。由两个乘数的符号异或得到。
②计算乘积的数值位。乘积的数值部分为两个乘数的数值部分之积。
实现算法：
具体实现：
注意：
C：用来保存进位
P：部分积（开始时，初始值为0）
Y：乘数（符号位单独处理）（x*y，y是乘数，x是被乘数）
符号位单独处理
2.补码乘法运算（符号位和数值位一起处理）
补码一位乘法：每次部分积是一位相乘得到的。
补码两位乘法：每次部分积都是两位相乘得到的。
Booth（布斯）乘法：将符号位与数值位合在一起参与运算，直接得出用补码表示的乘积，且正数和负数同等对待。
Booth乘法运算规则：
注意：逻辑右移是只补0，算数右移是最高位是啥就补啥。原码中是逻辑右移，补码中是算术右移（本人还是不确定，欢迎各位小伙伴告知哈）
九、定点除法运算
判断被除数和除数的取值和大小：
在进行定点数除法运算前，首先要对被除数和除数的取值和大小进行相应的判断，以确定除数是否是0、商是否为0、是否溢出等。通常的判断操作如下：
①若被除数为0、除数不为0，或者定点整数除法时 |被除数| < |除数| ，则说明商为0，余数为被除数，不再继续执行。
②若被除数不为0、除数为0，对于整数，则发生“除数为0”异常；对于浮点数，则结果为无穷大。
③若被除数和除数都为0，对于整数，则发生除法错异常；对于浮点数，则有些机器产生一个不发信号的NaN，即“quiet NaN”。
④只有当被除数和除数都不为0，并且商也不可能溢出（例如，补码中最大负数除以-1时会发生溢出）时，才进一步进行除法运算。
1.原码除法运算
计算机中两个无符号数除法的运算步骤和算法要点如下：
①操作数预置：在确认被除数和除数都不为0后，将被除数（必要时进行0扩展）置于余数寄存器R和余数/商寄存器Q中，除数置于除数寄存器Y中。
②做减法试商：根据R-Y得到的结果的符号来判断两数的大小。若结果为正，则上商1，若结果为负，则上商0.
③上商为0时恢复余数：把减掉的除数再加回来，恢复原来的中间余数。
④中间余数左移，以便继续试商：手算除法中，每次试商前，除数右移后，与中间余数进行比较。在计算机内部进行除法运算时，除数在除数寄存器中不动，因此，需要将中间余数左移，将左移结果与除数相减，以进行比较。左移时中间余数和商一起进行左移，Q的最低位空出，以备上商。
2.恢复余数除法
3.不恢复余数除法
4.补码除法运算
与补码加减运算、补码乘法运算一样，补码除法也可以将符号位和数值位合在一起进行运算，而且商符直接在除法运算中产生。对于两个n位补码除法，被除数需要进行符号扩展。若被除数为2n位，除数为n位，则被除数无需扩展。
同样，首先要对被除数和除数的取值、大小等进行相应的判断，以确定除数是否为0、商是否为0、是否溢出。
判断是否够减的规则：
当被除数（中间余数）与除数同号时做减法；异号时，做加法。若加减运算后得到的新余数与原余数符号一致（余数符号未变）则够减；否则不够减。
根据是否立即恢复余数，补码除法也分为恢复余数法和不恢复余数法两种。
十、浮点数运算
1.浮点数加减运算
IEEE 754提供了4种舍入模式：
（1）对阶
（2）尾数相加
（3）规格化
（4）舍入
（5）溢出判断
2.浮点数乘/除运算
浮点数乘法（除法）运算：
①尾数相乘（相除）、阶码相加（相减）
②尾数规格化
③尾数舍入处理
④阶码溢出判断
