二、进制与编码 - 江苏省句容高级中学

1、2011信息学奥赛基础知识（进制与编码）一、进制转换四种常用的数制及它们之间的相互转换：进制基数符号基数个数权进数规律十进制0、1、2、3、4、5、6、7、8、9D1010i逢十进一二进制0、1B22i逢二进一八进制0、1、2、3、4、5、6、7O88i逢八进一十六进制0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、FH1616i逢十六进一二进制数、八进制数、十六进制数转换为十进制数的方法：按权展开求和法十进制数转换为二进制数、八进制数、十六进制数的方法：整数部分短除法逆向取余，小数部分正向取整1二进制与十进制间的相互转换：（1）二进制转十进制 方法：“按权展开求和”例： （101

2、1.01）2 （1×230×221×211×200×211×22 ）10（802100.25）10（11.25）10规律：个位上的数字的次数是0，十位上的数字的次数是1，.，依次递增，而十分位的数字的次数是-1，百分位上数字的次数是-2，.，依次递减。 注意：不是任何一个十进制小数都能转换成有限位的二进制数。（2）十进制转二进制十进制整数转二进制数：“除以2取余，逆序排列”（短除反取余法） 例： （89）10 （1011001）22 892 44 12 22 02 11 02 5 12 2 12 1 00 1十进制小数转二进制数：“乘

3、以2取整，顺序排列”（乘2顺取整法） 2八进制与二进制的转换：二进制数转换成八进制数：从小数点开始，整数部分向左、小数部分向右，每3位为一组用一位八进制数的数字表示，不足3位的要用“0”补足3位，就得到一个八进制数。八进制数转换成二进制数：把每一个八进制数转换成3位的二进制数，就得到一个二进制数。例：将八进制的37.416转换成二进制数：3 7 4 1 6011 111 100 001 110即：（37.416）8 （11111.10000111）2 例：将二进制的10110.0011 转换成八进制： 0 1 0 1 1 0 . 0 0 1 1 0 0 2 6 . 1 4 即：（10110.0

4、11）2 （26.14）83十六进制与二进制的转换：二进制数转换成十六进制数：从小数点开始，整数部分向左、小数部分向右，每4位为一组用一位十六进制数的数字表示，不足4位的要用“0”补足4位，就得到一个十六进制数。十六进制数转换成二进制数：把每一个八进制数转换成4位的二进制数，就得到一个二进制数。例：将十六进制数5DF.9 转换成二进制： 5 D F 9 0101 1101 1111 1001 即：（5DF.9）16 （10111011111.1001）2 例：将二进制数1100001.111 转换成十六进制： 0110 0001 1110 6 1 E 即：（1100001.111）2 （61.

5、E）16注意：以上所说的二进制数均是无符号的数。这些数的范围如下表：无符号位二进制数位数数值范围十六进制范围表示法8位二进制数0255 （255=28-1）000FFH16位二进制数065535 （65535=216-1）0000H0FFFFH32位二进制数0232-100000000H0FFFFFFFFHBCD码 即BCD代码。Binary-Coded Decimal，简称BCD，称BCD码或二-十进制代码，亦称二进码十进数。是一种二进制的数字编码形式，用二进制编码的十进制代码。这种编码形式利用了四个位元来储存一个十进制的数码，使二进制和十进制之间的转换得以快捷的进行。这种编码技巧，最常用于

6、会计系统的设计里，因为会计制度经常需要对很长的数字串作准确的计算。相对于一般的浮点式记数法，采用BCD码，既可保存数值的精确度，又可免却使电脑作浮点运算时所耗费的时间。此外，对于其他需要高精确度的计算，BCD编码亦很常用。例：3 2 1 的BCD代码为0011 0010 0001二、原码、反码、补码 计算机中参与运算的数有正负之分，计算机中的数的正负号也是用二进制表示的。用二进制数表示符号的数称为机器码。常用的机器码有原码、反码和补码。 1、原码 求原码的方法：设X；若X0，则符号位（原码最高位）为0，X其余各位取值照抄；若X0，则符号位为1，其余各位照抄。【例1】X=+100100

7、1 X原 = 01001001 【例2】X=-1001001 X原 = 11001001 2、反码 求反码的方法：设X；若X0，则符号位（原码最高位）为0，X其余各位取值照抄；若X0，则符号位为1，其余各位按位取反。【例3】X=+1001001 X反 = 01001001 【例4】X=-1001001 X反 = 10110110 3、补码 求补码的方法：设X；若X0，则符号位（原码最高位）为0，X其余各位取值照抄；若X0，则符号位为1，其余各位按位取反后，最低位加1。【例5】X=+1001001 X补 = 01001001 【例6】X=-1001001 X补 = 10110111 4、补码加减

8、法 计算机中实际上只有加法，减法运算转换成加法运算进行，乘法运算转换成加法运算进行，除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。 1、补码加法 X+Y补 = X补 + Y补【例7】X=+0110011,Y=-0101001，求X+Y补 X补=00110011 Y补=11010111 X+Y补 = X补 + Y补 = 00110011+11010111=00001010 注：因为计算机中运算器的位长是固定的，上述运算中产生的最高位进位将丢掉，所以结果不是 100001010，而是00001010。 2、补码减法 X-Y补 = X补 - Y补 = X补 + -Y补 其中-Y补称为负

9、补，求负补的方法是：对补码的每一位（包括符号位）求反，最后末位加“1”。【例8】X=+0111001,Y=+1001101，求X-Y补 X补=00111001 Y补=01001101 -Y补 = 10110011 X-Y补 = X补 + -Y补 = 00111001+10110011=11101100 5、数的表示范围 通过上面的学习，我们就可以知道计算机如果用一个字节表示一个整数的时候，如果是无符号数，可以表示0255共256个数（0000000011111111），如果是有符号数则能表示-128127共256个数（1000000001111111）。如果两个字节表示一个整数，则共有6553

10、6个数可以表示，大部分程序设计语言中整数的范围都是-3276832767的原因，可以看出这种整数类型是16位的有符号数，而且是补码表示的。带符号数的机器码表示方法，n位范围是-2n-1到2n-1-1。下表列出的8位二进制原码，反码和补码并将补码用十六进制表示。真值原码（B）反码（B）补码（B）补码（H）+1270 111 11110 111 11110 111 11117F+390 010 01110 010 01110 010 011127+00 000 00000 000 00000 000 000000-01 000 00001 111 11110 000 000000-391 010

11、01111 101 10001 101 1001D9-1271 111 11111 000 00001 000 000181-128无法表示无法表示1 000 000080从上可看出，真值+0和-0的补码表示是一致的，但在原码和反码表示中具有不同形式。8位补码机器数可以表示-128，但不存在+128的补码与之对应，由此可知，8位二进制补码能表示数的范围是-128+127。还要注意，不存在-128的8位原码和反码形式。三、奇偶校验计算机中数据在进行存储和传输过程中可能会发生错误。为了及时发现和纠正这类错误，在数据传输（存储）过程中要进行校验，常用的校验方法就是奇偶校验。奇偶校验能发现一位或奇数位

12、错误，且不能纠正错误。一般以字节（八位二进制）为单位加1位奇偶校验位。奇偶校验分奇校验和偶校验两种。 奇校验：一个字节前面加一位校验位使得“1”的个数保持为奇数，若八位二进制数中“1”的个数为偶数，则校验位为“1”；若八位二进制数中“1”的个数为奇数，则校验位为“0”。【例1】给10011001 01101101加奇校验结果为110011001 001101101 偶校验：一个字节前面加一位校验位使得“1”的个数保持为偶数，若八位二进制数中“1”的个数为偶数，则校验位为“0”；若八位二进制数中“1”的个数为奇数，则校验位为“1”。【例2】给10011001 01101101加偶校验结果为010

13、011001 101101101四、信息存贮（一）定点数（Fixed-Point Number）计算机处理的数据不仅有符号，而且大量的数据带有小数，小数点不占有二进制一位而是隐含在机器数里某个固定位置上（实际不存在）。通常采取两种简单的约定：一种是约定所有机器数的小数的小数点位置隐含在机器数的最低位之后，叫定点纯整机器数，简称定点整数。另一种约定所有机器数的小数点隐含在符号位之后、有效部分最高位之前，叫定点纯小数机器数，简称定点小数。无论是定点整数，还是定点小数，都可以有原码、反码和补码三种形式。（二）浮点数（Floating-Point Number）计算机多数情况下采用作浮点数表示数值，它

14、与科学计数法相似，把一个二进制数通过移动小数点位置表示成阶码和尾数两部分：其中：EN的阶码（Expoent），是有符号的整数 SN的尾数（Mantissa），是数值的有效数字部分，一般规定取二进制定点纯小数形式。例：1011101B=2+7*0.1011101，101.1101B=2+3*0.1011101，0.01011101B=2-1*0.1011101浮点数的格式如下：E0E1E2En E0E1E2En 阶符 阶 尾符 尾数 浮点数由阶码和尾数两部分组成，底数2不出现，是隐含的。阶码的正负符号E0，在最前位，阶反映了数N小数点的位置，常用补码表示。二进制数N小数点每左移一位，阶

15、增加1。尾数是这点小数，常取补码或原码，码制不一定与阶码相同，数N的小数点右移一位，在浮点数中表现为尾数左移一位。尾数的长度决定了数N的精度。尾数符号叫尾符，是数N的符号，也占一位。例：写出二进制数-101.1101B的浮点数形式，设阶码取4位补码，尾数是8位原码。-101.1101=-0.1011101*2+3浮点形式为： 阶码0011 尾数11011101补充解释：阶码0011中的最高位“0”表示指数的符号是正号，后面的“011”表示指数是“3”；尾数11011101的最高位“1”表明整个小数是负数，余下的1011101是真正的尾数。例：计算机浮点数格式如下，写出x=0.0001101B的

16、规格化形式，阶码是补码，尾数是原码。x=0.0001101=0.1101*10-3 又-3补=-001B补=1011补=1101B110101101000所以 浮点数形式是 0 48 A 65 a 97ASCII码 ( American Standard Code for Information Interchange)美国标准信息交换代码，将每个字符用7位的二进制数来表示，共有128种状态汉字信息编码1汉字输入码（外码）汉字输入方法大体可分为：区位码（数字码）、音码、形码、音形码。· 区位码：优点是无重码或重码率低，缺点是难于记忆；· 音码：优点是大多数人都易于掌握，但同

17、音字多，重码率高，影响输入的速度；· 形码：根据汉字的字型进行编码，编码的规则较多，难于记忆，必须经过训练才能较好地掌握；重码率低；·音形码：将音码和形码结合起来，输入汉字，减少重码率，提高汉字输入速度。2汉字交换码汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。自国家标准GB231280公布以来，我国一直沿用该标准所规定的国标码作为统一的汉字信息交换码。GB231280标准包括了6763个汉字，按其使用频度分为一级汉字3755个和二级汉字3008个。一级汉字按拼音排序，二级汉字按部首排序。此外，该标准还包括标点符号、数种西文字母、图形

18、、数码等符号682个。由于GB231280是80年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字信息的产品采用新颁布的GB18030信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，可解决两岸三地间GB码与BIG5码间的字码转换不便的问题。3字形存储码字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模。一般的点阵规模有16×16，24×24，32×32，64×64等，每一个点在存储器中用一个二进制位（bit）存储。例如，在16×16的点阵中，需16×16bit=32 b

19、yte 的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。为了节省存储空间，普遍采用了字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息。五、运算法则二进制的算术运算 1、加法运算规则： 0+0=0 0+1=1 1+0=1 1+1=10 2、减法运算规则： 0-0=0 0-1=1（向高位借1） 1-0=1 1-1=0 3、乘法运算规则： 0×0=0 0×1=0 1×0=0 1×1=1 Pascal的运算符表达式是用运算符号或小括号将常量、变量、函数连接成的式子。Pascal表达式中只有小括号

20、。运算符也称为算符，算符的操作对象称为操作数。运算符按带操作数的个数分为两类：A. 单目运算符：对一个操作数操作。-（负号），+（正号）B. 双目运算符：对两个操作数操作。根据运算符运算的意义不同分为算术运算、布尔运算、逻辑运算、关系运算。根据运算符的优先级可以将运算符分为单目运算、“乘”的关系运算、“和”的关系运算、关系运算。算术运算符一共有8个。操作数都是数值型，结果也是数值型。单目运算符有（）取正、（）取负。双目运算符有（）加、（）减、（）乘、（/）除、（DIV）取商、（Mod）取余。1. “/” 左右的操作数是数值型，结果是实型数。2. Div 左右的操作数是整型，结果是整型（两数之商

21、）。3. Mod 左右的操作数是整型数，结果是整型数（两数相除之余）。4. 在PASCAL只有上面8种数学运算。其它的就只能利用这8种运算的组合通过语句来实现。如a2（a的平方）可以化成a*a。XY 可写成exp(y*ln(X)关系运算符系运算是指同一类型的两个数据进行比较，结果是一个布尔类型值。用小括号、>、<、>=、<=、=、<>将两个算术表达式连接起来的式子就称为关系表达式（比较式）。如：3+7>8,x+y<10,2*7<=13等都是关系表达式。布尔运算符布尔运算是对布尔型数据进行运算，即操作数都是布尔型数据，结果是布尔型。布尔型运算

22、符共有4个：not(取反) and(与) or(或) xor(异或)1. not ：结果是与操作数相反的布尔值2. and：两个操作数都为真，结果为真，否则为假3. or：两个操作有一个为真，结果为真，否则为假4. Xor:两个操作数不一样为真,否则为假运算符的优先级1. 内层小括号先计算2. 函数先求值3. 单目运算符（,not）4. 乘的关系双目运算符（*,/,div,mod,and）5. 加的关系双目运算符（,or）6. 关系运算符（<,<=,>,>=,=,<>）在同级运算中，按从左到右的顺序计算位运算    程

23、序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：   按位与参与运算的量，如果相对应的两位都为1，则该位的结果值为1，否则为0，即： 0 and 0=0 0 and 1=0 1 and 0=0 1 and 1=1 a 0001 0010 0011 0100 and b 0000 00