数值系统

进制系统

其他进制转十进制

基数和权的概念：如

$$1234.56 = 1\times10^3+2\times10^2+3\times10^1+4\times10^0+5\times10^{-1}+6\times10^-2$$

其中 1,2,3,4,5,6 叫做基数，10^n 叫做权，基数和权共同表示一个十进制数，若为 R 进制，则把 10 换成 R 即可

这种形式所对应的值为十进制的值

十进制转二进制

整数部分采用除 2 取余法，余数序列即为十进制的 2 进制表示，注意最上层是最低位，最下层是最高位，即这个序列是从右往左排的

• 建议直接看出来，如 36 = 32 + 4，直接化为 100100

小数部分采用乘 2 取整法，将小数不断乘以 2，取出其整数位，剩余小数继续乘以 2，直到没有小数位位置，这样取出的整数序列即为该小数对应的 2 进制，注意这里的序列是从左往右排的

• 对于无限循环小数，采用取精度的方式，如

0.1 会化为 00011 的循环，若取 6 位精度，则为 000110，同理若取 4 位精度，则为 0001

二进制转八/十六进制

以小数点为界，每三位 2 进制化为一个 8 进制数，每 4 位转化为一个 16 进制数

二	八	二	十六	二	十六
000	0	0000	0	1000	8
001	1	0001	1	1001	9
010	2	0010	2	1010	A
011	3	0011	3	1011	B
100	4	0100	4	1100	C
101	5	0101	5	1101	D
110	6	0110	6	1110	E
111	7	0111	7	1111	F

转化过程遵循整数左补零，小数右补零的原则

定点数表示和运算

定点数分为定点整数和定点小数，定点整数是纯整数，定点小数是纯小数，没有整数部分

机器数和真值

真值：以正负号带绝对值来表示一个数的真值

机器数：把符号数字转化为 0/1 码，这样的机器码叫做机器数，分为原码、补码、反码和移码

原码

带符号的绝对值表示，最高位 0 为正，1 为负

• 看正负，定最高位 1/0
• 加绝对值，将绝对值化为二进制
• 将符号位和绝对值拼接

将数变为原码是所有变化的第一步

反码

正数的反码为本身，负数的反码符号位不变，其余位按位取反，反码不具有任何意义，只是从原码到补码的一种中间状态

补码

正数的补码为其本身，负数的补码符号位不变，其余位按位取反并加一

移码

只能表示整数，规定最小值为 0，解决数据大小无法直观判断的问题

无论正负，把补码的符号位取反，即为移码

无符号数

无符号数的表示：每一位都用于表示数值的大小，即没有符号位，二进制长 n 位的无符号数的十进制表示范围为 0~2^n-1

• 十进制 2^n-1 ——> 二进制 n 个 1
• 对于无符号数，其最小值 -1 为最大值，最大值 +1 等于最小值
  • 最小值 -1 时，从更高位借位，借位标志记为 1
  • 最高值 +1 时，丢弃最高位，剩余位均为 0，进位标志记为 1

无符号数常用于表示内存概念

总结：快速转化

• 对于正数，原 = 反 = 补，符号位为 0，数值位等于其真值
• 对于负数，原码符号位为 1，数值部分等于其绝对值，反码为数值位取反，补码为反码加一
• 关于移码，无论正负，补码符号位取反得其移码
• 关于小数，在对二进制小数进行转化时，可以忽略其小数点，转化后按位加上即可

小技巧：求 36/128 的原码，相当于求 36/2^7 的原码，即先求 36 的原码，再将小数点左移 7 位，得 0.0100100，-36/128 同理，得 1.0100100

注意：0 的表示，+0 和 -0 的原码和反码并不一样，而补码和移码一样

机器数的表示范围

重点

二进制的比特数为 n+1，范围大小由十进制表示

机器码形式	整数	小数
原码	-(2^n-1), (2^n-1)	-(1-2^-n), (1-2^-n)
补码	-2^n, (2^n-1)	-1, (1-2^-n)
反码	-(2^n-1), (2^n-1)	-(1-2^-n), (1-2^-n)

补码比原、反码范围多一个数，是因为补码的 +0/-0 使用同一二进制表示，多出 100...000

注意整数 -1 和小数 -1 的补码表示并不相同？

移位运算

有符号数的移位称为算术移位，对无符号数的移位称为逻辑移位

左、右移会出现丢失位和空位的问题

• 逻辑移位

对于逻辑移位，即无符号数，左移时，高位丢低位补，右移时，低位丢高位补，以无效位(0)填充空位值

• 算术移位

符号不变，正数补 0；负数原码添 0，反码添 1，补码低位补 0，高位补 1

对于不进位的情况，取反和加一的结果是一样的，补码取反再加一，相当于右边某些位没有改变，相当于原码，而左侧即为反码，所以左移补低位为 0，右移补高位为 1

加减运算

补码加减

真正意义上只有加法没有减法，减法能够化为加法

由 [B]补 到 [-B]补 的转化：连同符号位，按位取反再加 1

二进制的加法逐位加即可，但这里涉及到溢出的问题，即运算结果超出合法表示范围

一位符号位：将符号位进位 Cs 和最高位进位 C1 进行异或（不同为 1），结果为 1 则为溢出

双符号位：正数符号 00，负数符号 11，若计算结果中符号位不为 00/11，则发生溢出

• 01 为正溢出
• 10 为负溢出

低位符号位参与移位，高符号位代表真正的符号

丢掉和溢出到底啥区别？

丢掉时直接将多的丢掉，啥也不管

溢出不考虑丢掉的位，考虑保存下的位数，比较最高位进位和符号位进位进行异或，判断是否溢出

小技巧 1：对于负数补码，用最小负数加上数值位即为其真值，如 10011011 = -128+1+2+8+16 = -101，或者化为原码再做判断

小技巧 2：对于补码，无论正负，1 多值大，1 靠左值大，其中 1 靠左优先级更大

浮点数表示和运算

定点数是纯整数或纯小数，浮点数指既有小数又有整数的数值，标准表示为：X = R^E x M

• E 是定点整数
• M 是定点小数
• R 是底数，和进制有关，2 或 10

浮点数的格式和范围

浮点数的一般格式

• k+1 位阶码，其中 1 位符号位，在阶码的最高位，0 为正，1 为负，表示 E
• n+1 位尾数，1 位符号为，n 位数值位，表示 M

当阶码 M 和尾数 E 的数值位均为 1 时，浮点数取到最大值？？？

$$2^{2^k-1}\times(1-2^{-n})$$

让尾数数值值为 +1，阶码达到最小，最小正数

$$2^{-2^k}\times2^{-n}$$

最小负数

$$2^{2^k-1}\times-1$$

最大负数

$$2^{-2^k}\times-2^{-n}$$

当大于最大正数，小于最小负数，称作上溢，报错

当小于最小正数，大于最大负数，称作下溢，记为机器零

机器零有两种情况，与机器能处理的字长有关系

• 尾数为 0
• 阶码小于等于其能达到的最小值

浮点数的规格化

对于

• 0.00123 x 10^2
• 0.0123 x 10^1
• 0.123 x 10^0

我们认为第三个精度最高，因为没有浪费位数

规格化定义：要求尾数的最高位必须是一个有效值

左规格化：尾数左移一位，阶码 -1

右规格化：尾数右移一位，阶码 +1，这种情况适用于双符号位发生溢出时采用，即双符号位为 01 或 10

• 左移相当于原浮点数乘以一个基数，阶码是指数，-1 相当于除以一个基数，保持原浮点数不变，右移同理

规格化遵循以下方法

• 非左溢右：非规格化左规格化，溢出右规格化
• 左减右加：对于阶码来说，左规格一位，阶码 -1，右规格化一位，阶码 +1
• 左多右一：左规格化可能移动多位，右规格化只可能移动一位

不同机器码的规格化形式

机器码	规格化形式
原码	尾数数值位第一位必须是 1
补码	尾数符号位与最高数值位必须不同

浮点数的运算

忽略基的情况下，要考虑指数和尾数进行分别处理，运算分为以下五步

• 对阶操作：小阶向大阶看齐

比较两个浮点数的阶码值大小，做差，求得阶差 e，将阶码小的浮点数的尾数数值位右移，每右移一次，阶码 +1，右移 e 位

移位时，高位补 0，低位丢弃，符号位不参与移位，这样浮点数的值不会变，但精度会变差

• 实现尾数的加减运算

对完成对阶后的浮点数执行求和/差操作，即对尾数进行相加减

• 规格化处理

对计算后的数据进行规格化处理，一般使用两位符号位表达，在运算后会得到以下六种结果

结果	处理
00.1xxxxx	\
11.0xxxxx	\
00.0xxxxx	左规（非左）
11.1xxxxx	左规
01.xxxxxx	右规（溢右）
10.xxxxxx	右规

还是那几个字，非左右溢，左减右加，左多右一

这里一定要多考虑两下，是否溢出？是否合规？

• 舍入操作：0 舍 1 入法

在进行对阶、右规格化时，有可能将低位的 1 移掉，为了相对保持精度，当舍去的最高位为 1 时（注意是舍去的最高位），将剩余的尾数最低位 +1，并依次进位

• 判溢出：看阶码

判断结果是否溢出，检查阶码的值是否超出给定范围

例题 P5 00::35:00，很复杂的计算，容易出错

当给出二进制原码 -0.1000111 时，直接按照规则换成补码 1.0111001

在进行加法运算时，若判断不好是否溢出，务必在两个数前多加一位符号位，在结果中通过两个结果符号位判断是否溢出

IEEE 754

在工业中，真正常用的标准：IEEE 754 标准

由 数符 + 阶码 + 尾数 构成

类型	数符	阶码	尾数数值	总位数	偏置值
短浮点数	1	8	23	32	7FH
长浮点数	1	11	52	64	3FFH

短浮点数和长浮点数在 IEEE 754 中长度是定义好的

十进制转 IEEE 浮点数

取到最大值

尾数用原码规格化表示，规定最高位为 1，并且通常会隐藏

阶码用类似移码的方式表示，阶码的真值加上一个偏移量，即偏置值

如对于十进制数 178.125

• 先化为二进制数 10110010.001
• 进行左移（规格化），令最高位为数符 1，得：1.0110010001 x 2^111
• 处理阶码 111，令其加上偏置值 7FH，得移码：00000111+01111111 = 10000110
• 因为默认尾数数符为 1，于是去掉最高位 1 得尾数：0.011010001

最后将 数符、阶码、尾数 拼接，得 IEEE 754 浮点数：0(数符)100 0011 0(阶码)011 0100 1000 0000 0000 0000(尾数)

其中尾数不够 23 位向右补 0

从 IEEE 754 化为十进制

• 阶码 -7F 得 a，作为 2 的指数
• 尾数补 1，通过基权相乘和得十进制数 b
• 根据数符添正负号，0 为正，1 为负

假设数符为 1，答案即为

$$-b\times2^a$$

单精度范围：1+8+23

$$\begin{aligned} step_{max} =& 1111 1110 =& 254\quad step_{min} =& 0000 0001 =& 1\\ tail_{max} =& 1.11...111 =& 2-2^{-23}\quad tail_{min} =& 1.00...000 =& 1 \end{aligned}$$

因为阶码要表示负数，所以 1-254 被分为 -126-127

对阶码和尾数进行组装，最小为最小拼接最小，最大为最大拼接最大

$$\begin{aligned} val_{max} =& 2^{127}\times(2-2^{-23})\\ val_{min} =& 2^{-126}\times 1 = 2^{-126} \end{aligned}$$

负数最大值为 -val(min)，最小值为 -val(max)，即取反即可

注意：

• 尾数虽然只有 23 位，但因为隐藏了 1 位，所以实际上可以表达 24 位
• 阶码为 1111 1111 时，表示上溢，0000 0000 表示下溢，所以有效范围是上式中表示

C 语言常用数据类型转换

在 c 语言中，整数使用补码表示，浮点数使用 IEEE 754 标准

在 c 语言中，系统会对各种类型数据进行自动、强制转换，实际上是基于数据长度，短转长属于自动转换，长转短属于强制转换

类型	char	short	int	long	float	double
长度(字节)	1	2	4	8	4	8

• 在实际运算时，字符型数据和 short 都是先转换为 int，再参与运算
• float 一律转换为 double 以提高运算精度

强制转换得一般形式：(类型说明符)(表达式)

有符号到无符号数相互转换

有符号 ——> 无符号，直接将符号位看作数值位即可

无符号 ——> 有符号，直接将最高数值位视作符号位即可

短数据和长数据相互转换

短转长：填充无效位

• 无符号数，用 0 填充
• 正数，用 0 填充
• 负数， 用 1 填充

长转短：直接截取低位即可，如 long 转换 int，直接截取低 32 位，就强制转换为 int，当然，有可能发生数据丢失

常用二进制和十进制对应关系，记住

二进制	十进制
2^10	1024
2^11	2048
2^12	4096
2^13	8192
2^14	16384
2^15	32768
2^16	65535

很重要：2^n 的二进制第 n+1 位是 1，其余位是 0；2^n-1 的二进制由 n 个 1 组成

• 有符号到无符号

  short si = -32767; 
  unsigned short usi = si;

si 原码为 1111 1111 1111 1111，补码为 1000 0000 0000 0001

无符号数 usi 将上述补码全视作数值位，得 usi = 32768+1 = 32769

• 短到长

  si = -8196;
  int i = si;

问 i 的机器码，易得 si 补码为 1101 1111 1111 1100，十六进制为 DFFC

此时强转成 int 类型，需要用无效位填充高 16 位，因为是负数，所以用 1 填充，故 i 机器码为：FFFF DFFC

短到长补位补符号数，即正补 0，负补 1

• 长到短到长

  int i = 65535;
  short si = short(i);
  int j = si;

• i = 65535(2^16-1) = 00FF 截取低 16 位给 short si，即 FF
• 因为 si 有符号，最高位为 1，表示其为负数，化为原码为 1000 0001，即为 -1
• si 扩 16 位变为 int j，因为是负数，填充无效位 1，同样化为原码，得到值 -1

于是 i = 65535，si = -1，j = -1

丢弃和溢出

先丢弃，再判溢出

如 32 位数据算出来了 33 位，先把最高位丢掉，再对剩下的数据判溢出

或者对 32 位数据手动加一位双符号位变成 33 位，这样有可能出现第 34 位，同理将第 34 位先丢弃，再对 33、32 位异或判断是否溢出

一些技巧

快速算负数补码

补码轮回的概念，如在 2 字节下，补码是 16 一轮回，-9 的补码是 16-9=7 的原码，一定是这样，当然这个原码是指数值位，并不包括符号位，如 10111 即为 -9 的补码，由符号 1 加上 7 的原码 0111 构成

又如，2 个字节，就是 2^8=256 一轮回，自然而然 -9 的补码是 1 加上 256-9=247 的原码

同理，这一过程逆向来看，若给定一个负数的补码，其值就为 轮回上限-原码 再添一个负号

总结来看

• 轮回上限 - 负数绝对值 = 数值位对应原码
• 轮回上限 - 数值位对应原码 = 负数绝对值

注意公式里的所有值计算都采用十进制

将这里的二进制补码用十六进制表示将更加明显，如 -9 的补码为 F7H，-8 的补码为 F8H，-1 的补码为 3FFH

又如补码 90H，其实际值 y 满足 FFH + y = 90H，得 y = -112

快速判断补码大小

对于正数，1 越多，越靠左，数值越大；对于负数，1 越多，越靠右，数值越小

• 其中靠左/右的优先级远大于 1 的数量

总结来看，无论正负，1 多值大，1 靠左值大，以此可以快速判断补码大小

快速浮点数大小判断

X = R^E x M

对于浮点数，其大小的决定性因素在于阶码 E，E 越多，浮点数的绝对值越大，这意味着

• 对于负数，E 越大，真实值越小
• 对于正数，E 越大，真实值越大

唯一的变数在于这个浮点数没有规格化，尾数瞎几把乱写，对于 IEEE 754 标准的浮点数，这个问题显然不存在（首位必为 1）