二、数据的表示和运算

二进制 Bin
十进制 Dec
八进制 Oct
十六进制 Hex（C语言中用 0x表示）

1.数值与编码

1.1数据存储和排列

在计算机系统内部，所有的信息都是用二进制进行编码的，这样做的原因有：

1. 二进制只有两种状态，使用有两个稳定状态的物理器件就可以表示二进制数的每一位，制造成本较低。
2. 二进制位1和0正好与逻辑值真和假对应，为计算机实现逻辑运算和程序中的逻辑判断提供了便利条件。
3. 二进制的编码和运算规则都很简单，通过逻辑门电路能方便地实现算术运算。

字符串存储时有大、小端之分。

边界对齐

• 进位计数法：

在进位计数法中，每个数位所用到的不同数码的个数称为基数，如10进制的基数为10。每个数码所表示的数值等于该数码本身乘以一个与它所在数位有关的常数，这个常数称为位权。一个进位数的数值大小就是它的各位数码按权相加。

• 码的权值：

有权码：例如BCD8421码、BCD2421码，每一位都有固定的权值
无权码：例如余三码，每一位的权值并不确定

eg.二进制的基数是2，计数符号是1和0，位权是2^n。

下面为十进制和二进制之间相互转换的简易方法：

❗1.2十进制转换

十进制转换中整数部分和小数部分分开进行转换。

1.2.1整数

• 下图演示了将十进制数字 36926 转换成八进制的过程：

从图中得知，十进制数字 36926 转换成八进制的结果为 110076。

• 下图演示了将十进制数字 42 转换成二进制的过程：

从图中得知，十进制数字 42 转换成二进制的结果为 101010。

1.2.2小数

• 下图演示了将十进制小数 0.930908203125 转换成八进制小数的过程：

从图中得知，十进制小数 0.930908203125 转换成八进制小数的结果为 0.7345。

• 下图演示了将十进制小数 0.6875 转换成二进制小数的过程：

从图中得知，十进制小数 0.6875 转换成二进制小数的结果为 0.1011。

1.3二进制转换

1.3.1 B->O

二进制整数转换为八进制整数时，每三位二进制数字转换为一位八进制数字，运算的顺序是从低位向高位依次进行，高位不足三位用零补齐。下图演示了如何将二进制整数 1110111100 转换为八进制：

1.3.2 B->H

二进制整数转换为十六进制整数时，每四位二进制数字转换为一位十六进制数字，运算的顺序是从低位向高位依次进行，高位不足四位用零补齐。下图演示了如何将二进制整数 10 1101 0101 1100 转换为十六进制：

1.4真值&机器数

+15，-8这种带+或-符号的数称为真值，真值是机器数所代表的实际值。

在计算机中，通常采用数的符号与数值一起编码的方法来表示数据，常用的有原码、补码、反码表示法。这几种表示法都将数据的符号数字化，通常用0表示正，用1表示负。

如0,101（逗号“，”并不实际存在，只是用来区分符号位与数值位，约定整数的数值位与符号位之间用逗号隔开，小数的符号位与数值位之间用小数点隔开）表示+5。这种把符号数字化的数称为机器数。

1.5 BCD码

binary-coded decimal，用二进制编码的十进制

• 8421

用4bit表示1个十进制0_9（00001001）

冗余6位，比如5+8=13（1101）这种超出9（1001）的数，再加6（0110）进行修正，得到0001 0011表示13

• 2421

0~4的第一位都是0
5~9的第一位都是1

原因：5（0101）（1011）两种都可表示，会出现歧义，所以只使用后者

• 余三码

是一种无权码。在8421码的基础上加上3，即0（0011），1（0100）

1.6 ASCII码

ASCII（American Standard Code for Information Interchange，美国信息互换标准代码）是一套基于拉丁字母的字符编码，共收录了 128 个字符，用一个字节就可以存储，它等同于国际标准 ISO/IEC 646。

2^7=128。用7bit就可以表示完全，不过1B（字节）=8bit，所以还要在高位补0。最早是7位，后来扩充为8位，在7位时期，为满足被8整除条件，需加1位空位才能使用

0~9的ASCII码值为48（011 0000）~57（011 1001），即去掉高3位，只保留低4位，正好是二进制形式的0~9。

a-z（97-122）A-Z（65-90）

a-A = 32，而32是空格。

其中0-31和127是控制字符，其他的才是可显示字符

二进制	十进制	十六进制	字符/缩写	解释
00000000	0	00	NUL (NULL)	空字符
00000001	1	01	SOH (Start Of Headling)	标题开始
00000010	2	02	STX (Start Of Text)	正文开始
00000011	3	03	ETX (End Of Text)	正文结束
00000100	4	04	EOT (End Of Transmission)	传输结束
00000101	5	05	ENQ (Enquiry)	请求
00000110	6	06	ACK (Acknowledge)	回应/响应/收到通知
00000111	7	07	BEL (Bell)	响铃
00001000	8	08	BS (Backspace)	退格
00001001	9	09	HT (Horizontal Tab)	水平制表符
00001010	10	0A	LF/NL(Line Feed/New Line)	换行键
00001011	11	0B	VT (Vertical Tab)	垂直制表符
00001100	12	0C	FF/NP (Form Feed/New Page)	换页键
00001101	13	0D	CR (Carriage Return)	回车键
00001110	14	0E	SO (Shift Out)	不用切换
00001111	15	0F	SI (Shift In)	启用切换
00010000	16	10	DLE (Data Link Escape)	数据链路转义
00010001	17	11	DC1/XON (Device Control 1/Transmission On)	设备控制1/传输开始
00010010	18	12	DC2 (Device Control 2)	设备控制2
00010011	19	13	DC3/XOFF (Device Control 3/Transmission Off)	设备控制3/传输中断
00010100	20	14	DC4 (Device Control 4)	设备控制4
00010101	21	15	NAK (Negative Acknowledge)	无响应/非正常响应/拒绝接收
00010110	22	16	SYN (Synchronous Idle)	同步空闲
00010111	23	17	ETB (End of Transmission Block)	传输块结束/块传输终止
00011000	24	18	CAN (Cancel)	取消
00011001	25	19	EM (End of Medium)	已到介质末端/介质存储已满/介质中断
00011010	26	1A	SUB (Substitute)	替补/替换
00011011	27	1B	ESC (Escape)	逃离/取消
00011100	28	1C	FS (File Separator)	文件分割符
00011101	29	1D	GS (Group Separator)	组分隔符/分组符
00011110	30	1E	RS (Record Separator)	记录分离符
00011111	31	1F	US (Unit Separator)	单元分隔符
00100000	32	20	(Space)	空格
00100001	33	21	!
00100010	34	22	"
00100011	35	23	#
00100100	36	24	$
00100101	37	25	%
00100110	38	26	&
00100111	39	27	’
00101000	40	28	(
00101001	41	29	)
00101010	42	2A	*
00101011	43	2B	+
00101100	44	2C	,
00101101	45	2D	-
00101110	46	2E	.
00101111	47	2F	/
00110000	48	30	0
00110001	49	31	1
00110010	50	32	2
00110011	51	33	3
00110100	52	34	4
00110101	53	35	5
00110110	54	36	6
00110111	55	37	7
00111000	56	38	8
00111001	57	39	9
00111010	58	3A	:
00111011	59	3B	;
00111100	60	3C	<
00111101	61	3D	=
00111110	62	3E	>
00111111	63	3F	?
01000000	64	40	@
01000001	65	41	A
01000010	66	42	B
01000011	67	43	C
01000100	68	44	D
01000101	69	45	E
01000110	70	46	F
01000111	71	47	G
01001000	72	48	H
01001001	73	49	I
01001010	74	4A	J
01001011	75	4B	K
01001100	76	4C	L
01001101	77	4D	M
01001110	78	4E	N
01001111	79	4F	O
01010000	80	50	P
01010001	81	51	Q
01010010	82	52	R
01010011	83	53	S
01010100	84	54	T
01010101	85	55	U
01010110	86	56	V
01010111	87	57	W
01011000	88	58	X
01011001	89	59	Y
01011010	90	5A	Z
01011011	91	5B	[
01011100	92	5C	\
01011101	93	5D	]
01011110	94	5E	^
01011111	95	5F	_
01100000	96	60	`
01100001	97	61	a
01100010	98	62	b
01100011	99	63	c
01100100	100	64	d
01100101	101	65	e
01100110	102	66	f
01100111	103	67	g
01101000	104	68	h
01101001	105	69	i
01101010	106	6A	j
01101011	107	6B	k
01101100	108	6C	l
01101101	109	6D	m
01101110	110	6E	n
01101111	111	6F	o
01110000	112	70	p
01110001	113	71	q
01110010	114	72	r
01110011	115	73	s
01110100	116	74	t
01110101	117	75	u
01110110	118	76	v
01110111	119	77	w
01111000	120	78	x
01111001	121	79	y
01111010	122	7A	z
01111011	123	7B	{
01111100	124	7C	|
01111101	125	7D	}
01111110	126	7E	~
01111111	127	7F	DEL (Delete)	删除

1.7汉字与GBK

汉字的表示和编码

汉字的编码包括汉字的输入编码、汉字内码、汉字字形码三种，它们是计算机中用于输入、内部处理和输出三种用途的编码。区位码用2字节(Byte)表示一个汉字，每字节用七位码。区位码是4位十进制数，前2位是区码，后2位是位码，所以称为区位码。

如汉字“学”的区位码为4907（十进制），用2个字节的二进制可以表示为00110001 00000111。

国标码将10进制的区位码转换为16进制数后，再在每字节上加上20H。国标码两字节的最高位都是0，ASCII码的最高位也为0。为了便于区分中文和英文字符，将国标码两字节的最高位都改为1，这就是汉字内码

区位码和国标码都是输入码，它们与汉字内码的关系（16进制）为：

国标码=（区位码）16+2020H  汉字内码=（国标码）16+8080H

最早制定的汉字编码是GB2312，包括6763个汉字和682个其它符号 95年重新修订了编码，命名GBK1.0，共收录了21886个符号。 之后又推出了GBK18030编码，共收录了27484个汉字，同时还收录了藏文、蒙文、维吾尔文等主要的少数民族文字，现在windows平台必需要支持GBK18030编码。

区内码->国标码->汉字机内码

1.8 UTF

(也就是unicode编码)：俗称万国码，致力于使用统一的编码准则表达各国的文字。 为表达更多的文字，utf-8采用2/3混编的方式。目前容纳的汉字范围小于gbk编码。并且以 3字节的方式处理中文，带来了兼容性的问题。

1.9检错码

校验码是指能够发现或能自动纠正错误的数据编码，也称检错纠错编码。校验码的原理是通过增加一些冗余码，来检验或纠错编码。

通常某种编码都由许多码字构成，任意两个合法码字之间最少变化的二进制位数（在一种编码系统中，任意两组合法代码之间的最少二进制位数的差异），称为数据校验码的码距（或称编码的最小距离）（如1100和1101之间的码距为1，因为只有最低位翻转了。而1001和0010之间的码距为3，因为只有1位没有变化）。对于码距不小于2的数据校验码，开始具有检错的能力。码距越大，检错、纠错的能力越强，而且检错能力总是大于等于纠错能力。

• 检错编码：只是发现有错误，不能纠错，只能重传。
  • 奇偶校验码
  • 循环冗余码CRC
• 纠错编码 海明码：不仅能发现错误，还能知道是哪一个地方发生错误。

1.9.1奇偶校验码

前面加校验元1/0

要发送的信息 D 有 d 个比特。

在偶校验方案中，发送方只需包含一个附加的比特，选择附加比特的值，使得这 d+1 个比特(初始信息加上一个校验比特)中 1 的总数是偶数。

接收方的操作也很简单。接收方只需要数一数接收的 d+1 比特中 1 的个数。
如果发现了奇数个值为 1 的比特，接收方知道了至少出现了一个比特差错。更确切的说法是，出现了奇数个差错比特。但是如果出现了偶数个比特差错，显然这种方法无法检测这种错误。

eg: 如果1001101有4个1，所以在前面加0，保持偶数个1：0,1001101。

如果1001100有3个1，所以在前面加1，变成1,1001101。

奇校验：

1001101有4个，所以在前面加1，变成奇数个1：1,1001101。

二维单比特奇偶校验方案中，D 中的 d 个比特被划分为 i 行 j 列。对每行和每列计算奇偶值。产生的 i+j+1 奇偶比特构成了链路层帧的差错检测比特。这种方法可以检测和纠正 1 比特的错误。

用一位奇偶校验能检测出一位主存错误的百分比为（）
  A.0   B.1   C.0.5   D.无法计算

答案：B；
若出现一位主存错误，一定能检测出

1.9.2循环冗余检测CRC

在数据发送之前，按照某种关系附加上一定的冗余码，构成一个符合某一个规则的码字之后再发送。当发送的数据发生变化时，冗余码也发生变化，使其不再遵守规则。接收端通过检验是否符合规则判断是否出错。

CRC 编码也称为多项式编码，因为该编码将要发送的比特串看作是系数为 0 和 1 的一个 多项式，对比特串的操作被解释为多项式运算。

发送端：

要传的数据		生成多项式		冗余码/帧检验序列FCS
5	%	2	= 2 …	1

5%2=2…1

最终发送的数据是，要发送的数据+真检测序列FCS。这里就是5+1=6

接收端：

6%2=3…0（余数是0，判定无错，就接受）

计算冗余码FCS步骤：

1. 在要传的数据后加0。
2. 模2除法。
3. 最终发送的数据：要发送的数据+FCS。

如果余数为0，判定这个帧没有差错。（接受）

如果余数不为0，判定这个帧有差错。（丢弃）

FCS的生成以及接收端CRC检验都是由硬件实现的，处理很迅速，不会产生延迟数据。

只使用CRC：凡是接收端数据链路层接受的帧均无差错。能够实现无比特差错的传输，但不是可靠传输（因为错误的帧丢弃了，接收端并没有收到）。

可靠传输：数据链路层发什么，接收端就接收什么。

例题：在CRC中，接收端检测出某一位数据错误后，纠正的方法是（）
  A.请求重发   B.删除数据   C.通过余数值自行纠正   D.以上均可

答案：D；CRC可以纠正一位或多位错误（由多项式G（x）决定），而实际传输中纠正方法可以按需求进行选择，在计算机网络中，ABC三种方法都是很常见的

例题：说明CRC码的纠错原理和方法。对4位有效信息（1100）求循环校验码，选择生成多项式（1011）

答案：在CRC码中，选择适当的生成多项式G（x），在计算机二进制信息M（x）的长度确定时，余数与CRC出错位的对应关系是不变的，因此可以用余数作为判断出错位置的依据而纠正错码。CRC码的检错方法如下：接受数据时，将接收的CRC码与G（x）相除，若余数为0，则表明数据正确；若余数不为0，说明数据有错。若G（x）选择适当，余数还可以判断出错的位置，从而实现纠错。

1100的循环校验码为1100 010

1.9.3海明（汉明）码

海明码实际上是一种多重奇偶校验码。其实现原理是在有效信息位中加入几个校验位形成海明码，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错位，还能指出错位的位置。汉明码有一位纠错能力。

可以发现双比特错，但是只能纠正单比特错。

工作原理：动一发而牵全身：L-1=D+C且D>=C

工作流程：

1. 确认校验码位数r

   n为有效信息位数，k为校验位的位数，则n和k应满足海明不等式n+k<=2^k-1。

2. 确定校验码和数据的位置

3. 求出校验码的值

4. 检错并纠错

海明不等式：
$$2^r\ge k+r+1$$
r：冗余信息位（校验码位数）
k：信息位（原始数据的位数）

例子：数据D=101101
∴ 数据位数k=6
∵ 海明不等式
∴ 满足不等式的最小r=4
∴ D的海明码应该有6+4=10位
其中原数据6位，效验码4位

校验码是插入原数据之中的，而且，只能放在2的几次方的位置

设4位效验码依次是p1, p2, p3, p4，则它们放在

位数	1	2	3	4	5	6	7	8	9	10
二进制	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010
代码	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6
实际值	0	0	1	0	0	1	1	1	0	1

一个校验码可以校验多位数据：

p1的二进制位1在末尾，所以它可以效验1在末尾的数据。
求p1。令所有要校验的位异或为0：p1⊕d1⊕d2⊕d4⊕d5=0
将代码对应的实际值代入，得到p1=0

同理，p2的1在第二位，p2⊕d1⊕d3⊕d4⊕d6=0，p2=0

p3=0，p4=1

所以，D=101101的海明码就是0010011101

当接收方收到时候，就会重复上述异或过程，就会检查出那个比特出错了。