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

2011信息学奥赛基础知识

（进制与编码）

一、进制转换

四种常用的数制及它们之间的相互转换： 进制 基数 符号 基数个数 权 进数规律 十进制 0、1、2、3、4、5、6、7、8、9 D 10 10i 逢十进一 二进制 0、1 B 2 2i 逢二进一 八进制 0、1、2、3、4、5、6、7 O 8 8i 逢八进一 0、1、2、3、4、5、6、7、8、9、十六进制 H 16 16i 逢十六进一 A、B、C、D、E、F 二进制数、八进制数、十六进制数转换为十进制数的方法：按权展开求和法 十进制数转换为二进制数、八进制数、十六进制数的方法：整数部分短除法—逆向取余，小数部分—正向取整

1．二进制与十进制间的相互转换：

（1）二进制转十进制 方法：“按权展开求和”

例： （1011.01）2 ＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2 ）10

＝（8＋0＋2＋1＋0＋0.25）10＝（11.25）10

规律：个位上的数字的次数是0，十位上的数字的次数是1，......，依次递增，而十 分位的数字的次数是-1，百分位上数字的次数是-2，......，依次递减。 注意：不是任何一个十进制小数都能转换成有限位的二进制数。 （2）十进制转二进制 十进制整数转二进制数：“除以2取余，逆序排列”（短除反取余法） 例： （）10 ＝（1011001）2

2

2 44 „„1 2 22 „„0 2 11 „„0 2 5 „„1 2 2 „„1 2 1 „„0 0 „„1

十进制小数转二进制数：“乘以2取整，顺序排列”（乘2顺取整法）

2．八进制与二进制的转换：

二进制数转换成八进制数：从小数点开始，整数部分向左、小数部分向右，每3位为一组用一位八进制数的数字表示，不足3位的要用“0”补足3位，就得到一个八进制数。

八进制数转换成二进制数：把每一个八进制数转换成3位的二进制数，就得到一个二进制数。

例：将八进制的37.416转换成二进制数： 3 7 ． 4 1 6 011 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.011）2 ＝ （26.14）8

3．十六进制与二进制的转换：

二进制数转换成十六进制数：从小数点开始，整数部分向左、小数部分向右，每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.E）16

注意：以上所说的二进制数均是无符号的数。这些数的范围如下表： 无符号位二进制数位数值范围 十六进制范围表示法 数 8位二进制数 0~255 （255=28-1） 00~0FFH 16位二进制数 0~65535 （65535=216-1） 0000H~0FFFFH 32位二进制数 0~232-1 00000000H~0FFFFFFFFH BCD码 即BCD代码。Binary-Coded Decimal‎，简称BCD，称BCD码或二-十进制代码，亦称二进码十进数。是一种二进制的数字编码形式，用二进制编码的十进制代码。这种编码形式利用了四个位元来储存一个十进制的数码，使二进制和十进制之间的转换得以快捷的进行。这种编码技巧，最常用于会计系统的设计里，因为会计制度经常需要对很长的数字串作准确的计算。相对于一般的浮点式记数法，采用BCD码，既可保存数值的精确度，又可免却使电脑作浮点运算时所耗费的时间。此外，对于其他需要高精确度的计算，BCD编码亦很常用。例：3 2 1 的BCD代码为 0011 0010 0001 二、原码、反码、补码

计算机中参与运算的数有正负之分，计算机中的数的正负号也是用二进制表示的。用二进制数表示符号的数称为机器码。常用的机器码有原码、反码和补码。 1、原码

求原码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位照抄。

【例1】X=+1001001 [X]原 = 01001001 【例2】X=-1001001 [X]原 = 11001001 2、反码

求反码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位按位取反。

【例3】X=+1001001 [X]反 = 01001001 【例4】X=-1001001 [X]反 = 10110110 3、补码

求补码的方法：设X；若X≥0，则符号位（原码最高位）为0，X其余各位取值照抄；若X≤0，则符号位为1，其余各位按位取反后，最低位加1。

【例5】X=+1001001 [X]补 = 01001001 【例6】X=-1001001 [X]补 = 10110111 4、补码加减法

计算机中实际上只有加法，减法运算转换成加法运算进行，乘法运算转换成加法运算进行，除法运算转换成减法运算进行。用补码可以很方便的进行这种运算。 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]补称为负补，求负补的方法是：对补码的每一位（包括符号位）求反，最后末位加“1”。 【例8】X=+0111001,Y=+1001101，求[X-Y]补

[X]补=00111001 [Y]补=01001101 [-Y]补 = 10110011

[X-Y]补 = [X]补 + [-Y]补 = 00111001+10110011=11101100

5、数的表示范围

通过上面的学习，我们就可以知道计算机如果用一个字节表示一个整数的时候，如果是无符号数，可以表示0~255共256个数（00000000~11111111），如果是有符号数则能表示-128~127共256个数（10000000~01111111）。如果两个字节表示一个整数，则共有65536个数可以表示，大部分程序设计语言中整数的范围都是-32768~32767的原因，可以看出这种整数类型是16位的有符号数，而且是补码表示的。

n-1n-1

带符号数的机器码表示方法，n位范围是-2到2-1。

下表列出0,39,127及128的8位二进制原码，反码和补码并将补码用十六进制表示。

真值 原码（B） 反码（B） 补码（B） 补码（H） +127 0 111 1111 0 111 1111 0 111 1111 7F +39 0 010 0111 0 010 0111 0 010 0111 27 +0 0 000 0000 0 000 0000 0 000 0000 00 -0 1 000 0000 1 111 1111 0 000 0000 00 -39 1 010 0111 1 101 1000 1 101 1001 D9 -127 1 111 1111 1 000 0000 1 000 0001 81 -128 无法表示 无法表示 1 000 0000 80 从上可看出，真值+0和-0的补码表示是一致的，但在原码和反码表示中具有不同形式。8位补码机器数可以表示-128，但不存在+128的补码与之对应，由此可知，8位二进制补码能表示数的范围是-128——+127。还要注意，不存在-128的8位原码和反码形式。

三、奇偶校验

计算机中数据在进行存储和传输过程中可能会发生错误。为了及时发现和纠正这类错误，在数据传输（存储）过程中要进行校验，常用的校验方法就是奇偶校验。

奇偶校验能发现一位或奇数位错误，且不能纠正错误。一般以字节（八位二进制）为单位加1位奇偶校验位。奇偶校验分奇校验和偶校验两种。

奇校验：一个字节前面加一位校验位使得“1”的个数保持为奇数，若八位二进制数中“1”的个数为偶数，则校验位为“1”；若八位二进制数中“1”的个数为奇数，则校验位为“0”。

【例1】给10011001 01101101加奇校验结果为110011001 001101101 偶校验：一个字节前面加一位校验位使得“1”的个数保持为偶数，若八位二进制数中“1”的个数为偶数，则校验位为“0”；若八位二进制数中“1”的个数为奇数，则校验位为“1”。

【例2】给10011001 01101101加偶校验结果为010011001 101101101 四、信息存贮

（一）定点数（Fixed-Point Number）

计算机处理的数据不仅有符号，而且大量的数据带有小数，小数点不占有二进制一位而是隐含在机器数里某个固定位置上（实际不存在）。通常采取两种简单的约定：一种是约定所有机器数的小数的小数点位置隐含在机器数的最低位之后，叫定点纯整机器数，简称定点整数。另一种约定所有机器数的小数点隐含在符号位之后、有效部分最高位之前，叫定点纯小数机器数，简称定点小数。无论是定点整数，还是定点小数，都可以有原码、反码和补码三种形式。

（二）浮点数（Floating-Point Number）

计算机多数情况下采用作浮点数表示数值，它与科学计数法相似，把一个二进制数通过移动小数点位置表示成阶码和尾数两部分：

E N2S

其中：E——N的阶码（Expoent），是有符号的整数 S——N的尾数（Mantissa），是数值的有效数字部分，一般规定取二进制定点纯小数形式。 例：1011101B=2+7*0.1011101，101.1101B=2+3*0.1011101，0.01011101B=2-1*0.1011101 浮点数的格式如下： E0 E1E2„„„„„ E0 E1E2„„„„„En En

阶符 阶 尾符 尾数

浮点数由阶码和尾数两部分组成，底数2不出现，是隐含的。阶码的正负符号E0，在最前位，阶反映了数N小数点的位置，常用补码表示。二进制数N小数点每左移一位，阶增加1。尾数是这点小数，常取补码或原码，码制不一定与阶码相同，数N的小数点右移一位，在浮点数中表现为尾数左移一位。尾数的长度决定了数N的精度。尾数符号叫尾符，是数N的符号，也占一位。

例：写出二进制数-101.1101B的浮点数形式，设阶码取4位补码，尾数是8位原码。

-101.1101=-0.1011101*2

浮点形式为： 阶码0011 尾数11011101 补充解释：阶码0011中的最高位“0”表示指数的符号是正号，后面的“011”表示指数是“3”；尾数11011101的最高位“1”表明整个小数是负数，余下的1011101是真正的尾数。例：计算机浮点数格式如下，写出x=0.0001101B的规格化形式，阶码是补码，尾数是原码。

-3

x=0.0001101=0.1101*10 又[-3]补=[-001B]补=[1011]补=1101B 所以 浮点数形式是 1 101 0 1101000

ASCII码 ( American Standard Code for Information Interchange)美国标准信息交换代码，将每个字符用7位的二进制数来表示，共有128种状态

‘ 0 ’― 48 汉字信息编码 ‘ A ’― 65 1．汉字输入码（外码） ‘ a ’― 97 汉字输入方法大体可分为：区位码（数字码）、音码、形码、音形码。 · 区位码：优点是无重码或重码率低，缺点是难于记忆；

· 音码：优点是大多数人都易于掌握，但同音字多，重码率高，影响输入的速度；

· 形码：根据汉字的字型进行编码，编码的规则较多，难于记忆，必须经过训练才能较好地掌握；重码率低； ·音形码：将音码和形码结合起来，输入汉字，减少重码率，提高汉字输入速度。 2．汉字交换码

汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。自国家标准GB2312－80公布以来，我国一直沿用该标准所规定的国标码作为统一的汉字信息交换码。

GB2312－80标准包括了6763个汉字，按其使用频度分为一级汉字3755个和二级汉字3008个。一级汉字按拼音排序，二级汉字按部首排序。此外，该标准还包括标点符号、数种西文字母、图形、数码等符号682个。

由于GB2312－80是80年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字信息的产品采用新颁布的GB18030信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，可解决两岸三地间GB码与BIG5码间的字码转换不便的问题。 3．字形存储码

字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模。一般的点阵规模有16×16，24×24，32×32，×等，每一个点在存储器中用一个二进制位（bit）存储。例如，在16×16的点阵中，需16×16bit=32 byte 的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。

为了节省存储空间，普遍采用了字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息。 五、运算法则

二进制的算术运算 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表达式中只有小括号。运算符也称为算符，算符的操作对象称为操作数。 运算符按带操作数的个数分为两类：

A. 单目运算符：对一个操作数操作。-（负号），+（正号） B. 双目运算符：对两个操作数操作。

根据运算符运算的意义不同分为算术运算、布尔运算、逻辑运算、关系运算。 根据运算符的优先级可以将运算符分为单目运算、“乘”的关系运算、“和”的关系运算、关系运算。 算术运算符

一共有8个。操作数都是数值型，结果也是数值型。单目运算符有（＋）取正、（－）取负。双目运算符有（＋）加、（－）减、（＊）乘、（/）除、（DIV）取商、（Mod）取余。

1. “/” 左右的操作数是数值型，结果是实型数。 2. Div 左右的操作数是整型，结果是整型（两数之商）。

3. Mod 左右的操作数是整型数，结果是整型数（两数相除之余）。

4. 在PASCAL只有上面8种数算。其它的就只能利用这8种运算的组合通过语句来实现。如a^2（a

的平方）可以化成a*a。XY 可写成exp(y*ln(X))

关系运算符

系运算是指同一类型的两个数据进行比较，结果是一个布尔类型值。

用小括号、>、<、>=、<=、=、<>将两个算术表达式连接起来的式子就称为关系表达式（比较式）。如：3+7>8,x+y<10,2*7<=13等都是关系表达式。 布尔运算符

布尔运算是对布尔型数据进行运算，即操作数都是布尔型数据，结果是布尔型。 布尔型运算符共有4个：not(取反) and(与) or(或) xor(异或)

+3

1. not ：结果是与操作数相反的布尔值

2. and：两个操作数都为真，结果为真，否则为假 3. or：两个操作有一个为真，结果为真，否则为假 4. Xor:两个操作数不一样为真,否则为假 运算符的优先级

1. 内层小括号先计算 2. 函数先求值

3. 单目运算符（＋,－,not）

4. 乘的关系双目运算符（*,/,div,mod,and） 5. 加的关系双目运算符（＋,－,or） 6. 关系运算符（<,<=,>,>=,=,<>） 在同级运算中，按从左到右的顺序计算 位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，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 0000 1111 1111 c 0000 0000 0011 0100 按位或

参与运算的量，如果相对应的两位都为0，则该位的结果值为0，否则为1，即：

0 or 0=0 0 or 1=1 1 or 0=1 1 or 1=1

a 0001 0010 0011 0100 or b 0000 0000 1111 1111 c 0001 0010 1111 1111 按位异或

如果相对应的两位相异，则该位的结果为1，否则为0，即： 0 xor 0=0 0 xor 1=1 1 xor 0=1 1 xor 1=0 a 0001 0010 0011 0100 xor b 0000 0000 1111 1111 c 0001 0010 1100 1011 按位取反

将参与运算量的相对应位的值取反，即1变0，0变1。

not a 0001 0010 0011 0100 c 1110 1101 1100 1011 按位左移

按位左移是将一个运算量的各位依次左移若干位，低位补0，高位舍弃不要。 假设机器字长为8位，变量a的值为16，将a左移二位，即a=a shl 2： 左移前 0001 0000 左移后 0100 0000

由此看出，左移一位相当于该数乘2，左移二位相当于乘4，即22，但这要以该数左移之后不“溢出”为前提。所谓“溢出”指该数已超过机器字长所能容纳的范围，如该例若继续左移二位，该数为16× 24=256，超出了字长8位的表示范围（257），即产生了溢出。 按位右移

按位右移是将一个运算量的各位依次右移若干位，低位被移出，高位对无符号数补0，对有符号数要按最高符号位自身填补。

右移一位相当于该数除以2，但有可能带来误差。假设机器字长为8位，变量a值为15，将a右移二位，即a=a shr 2：

右移前 0000 1111

右移后 0000 0011