计算机基础之整数和浮点数

计基之整数和浮点数

Author： Once day date：2022年7月27日

漫漫长路才刚刚开始，不要甘于平凡。

1. 引言

每台计算机都有一个字长(word size)，指明指针数据的标称大小(nominal size)。

其虚拟地址范围和字长的关系如下：
$$addr=[0,2^w-1]$$
字节顺序：

小端法：在内存中按照最低有效字节到最高有效字节的顺序存储对象。

大端法：按照最高有效字节到最低有效字节的顺序存储。

布尔代数的布尔环：(a^b)^a=b

2.移位运算

左移位：没有歧义，左端舍弃，右端补0。

右移位：有两种，逻辑右移和算术右移。

• 逻辑右移：在左端补0，右端丢弃。
• 算术右移：左端补最高有效位的值，右端丢弃。

以下是示例：

c语言标准未定义有符号数使用右移的类型，但常见编译器使用算术右移。

当位移量很大时，一般遵守规则：移动位数k不超过数据的最大表示位数w，即k mod w.

3.整数的表示

3.1 无符号数编码的定义

对向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$存在：
$$B2U_w(\vec{x})=\sum _{i=0}^{w-1}{x}_i{2}^i$$
$B2U_w()$函数将一个长度为w的0/1串映射到非负整数。

因此w位向量最大值为：
$$UMa{x}_w=\sum _{i=0}^{w-1}{2}^i=2^w-1$$
无符号数的编码具有唯一性，即每个位于$[0,2^w-1]$之间的数都有唯一一个w为的值编码。

3.2 有符号数编码的定义

补码(two’s-complement)：将最高有效位解释为负权(negative weight)。

对向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$存在：
$$B2T_w(\vec{x})=-x_{w-1}{2}^{w-1}+\sum _{i=0}^{w-2}{x}_i{2}^i$$
最高有效位也成为了符号位。其极值为：
$$\begin{gathered} TMa{x}_w=-0\ast 2^{w-1}+\sum _{i=0}^{w-2}{2}^i=2^{w-1}-1 \\ TMi{n}_w=-1\ast 2^{w-1}+\sum _{i=0}^{w-2}0\ast 2^i=-2^{w-1} \end{gathered}$$
有符号数的编码同样具有唯一性！

反码(One’s Complement)：最高有效位权重是$-(2^{w-1}-1)$
$$B2O_w(\vec{x})=-x_{w-1}(2^{w-1}-1)+\sum _{i=0}^{w-2}{x}_i{2}^i$$
原码(Sign-Magnitude)：最高有效位是符号位，用确定正负号。
$$B2S_w(\vec{x})=(-1{)}^{x_{w-1}}\cdot (\sum _{i=0}^{w-2}{x}_i{2}^i)$$
这两种表示法都会产生一个问题，那就是0有两种表示方式。

3.3 有符号数和无符号数的转换(位数相同)

强制转换的结果是保持位值不变，只是重新改变了解释这些位的方式。

补码转换为无符号数可表示为如下：
T 2 U w ( x ) = { x + 2 w x < 0 x x ≥ 0 T2U_w(x)=

T2Uw​(x)={x+2wx​x<0x≥0​
显而易见，一个小负数，将被转化为很大的正数。

无符号数转换为补码：
U 2 T w ( u ) = { u x ≤ T M a x w u − 2 w x > T M a x w U2T_w(u)=

U2Tw​(u)={uu−2w​x≤TMaxw​x>TMaxw​​
在c标准库文件里limits.h，INT_MIN = (-INT_MAX -1)=-2147483647-1。

这是一种很保守的表示方法。

3.4 扩展一个数字的位表示

无符号数的零扩展：

对w位向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$扩展到w‘位向量$\overrightarrow{x^{\prime }}=[0,0,...,0,0,x_{w-1},x_{w-2},...,x_0]$。

只需要在开头添加零即可。

符号数的符号扩展：

对w位向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$扩展到w‘位向量$\overrightarrow{x^{\prime }}=[x_{w-1},...,x_{w-1},x_{w-1},x_{w-2},...,x_0]$。

在表示中添加最高有效位，其值保持不变。

在C语言标准中：

如果将short值转换为unsigned int值，那么其转换顺序为：(unsigned int)(int) short_value。

3.5 截断数字

截断一个数字时，会直接丢弃高位。

无符号数的截断：

对w位向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$截断到k位向量$\overrightarrow{x^{\prime }}=[x_{k-1},x_{k-2},...,x_0]$。

对于其值，则有$x^{\prime }=x\mathrm{mod}{2}^k$

补码有符号数截断：

对w位向量$\vec{x}=[x_{w-1},x_{w-2},...,x_0]$截断到k位向量$\overrightarrow{x^{\prime }}=[x_{k-1},x_{k-2},...,x_0]$。

对于其值，则有$x^{\prime }=U2T_k(x\mathrm{mod}{2}^k)$。

相当于重新解释最高位为符号位。

3.6 无符号数运算

溢出的位直接丢弃：
0 ≤ x , y ≤ 2 w x + y = { x + y x + y < 2 w x + y − 2 w 2 w ≤ x + y < 2 w + 1 0\le x,y \le 2^w\\ x+y=

0≤x,y≤2wx+y={x+yx+y−2w​x+y<2w2w≤x+y<2w+1​
C程序不会将溢出作为错误而发信号。

可采用以下方法检测溢出:

• 当$0\le x,y \le 2^w\$时，s=x+y，当且仅当s

模数加法形成了一种数学结构，成为阿贝尔群。

无符号求反，即加法逆元-x：
− x = { x x = 0 2 w − x x > 0 -x=

−x={x2w−x​x=0x>0​
无符号乘法如下：
$$x\ast y=(x\ast y)\mathrm{mod}{2}^w$$

3.7 补码加法

两个数的w位补码之和与无符号数之和有完全相同的位级表示。
− 2 w − 1 ≤ x , y ≤ 2 w − 1 − 1 x + y = { x + y − 2 w 2 w − 1 ≤ x + y x + y − 2 w − 1 ≤ x + y < 2 w − 1 x + y + 2 w x + y < − 2 w − 1 -2^{w-1}\le x,y \le 2^{w-1}-1\\ x+y=

−2w−1≤x,y≤2w−1−1x+y=⎩ ⎨ ⎧​x+y−2wx+yx+y+2w​2w−1≤x+y−2w−1≤x+y<2w−1x+y<−2w−1​
检测补码加法中的溢出：

对满足$-2^{w-1}\le x,y\le 2^{w-1}-1$的x和y，令s=x+y，当且仅当x>0，y>0，但s≤0时，计算s发生了正溢出。

当且仅当x<0，y<0，但s≥0时，计算s发生了负溢出。

补码的一个奇特的规律：
$$TMi{n}_w+TMi{n}_w=-2^{w-1}+(-2^{w-1})=0$$
即补码非运算有：
− x = { T M i n w x = T M i n w − x x > T M i n w -x=

−x={TMinw​−x​x=TMinw​x>TMinw​​
在C语言中可以表达成：

-x = ~x + 1;
1

补码乘法如下：
$$x\ast y=U2T_w((x\ast y)\mathrm{mod}{2}^w)$$
即将高于w位的乘积截断，再以有符号数的编码来解释位级含义。

无符号和补码乘法的低w位位级表示是相同的。推导省略…

3.8 乘以常数的优化

可以使用移位运算来优化乘以2的幂次倍运算。
$$x\ast 2^k=x<<k$$
对于无符号数和补码数都成立。

3.9 除以2的幂的除法

可以使用移位运算来优化乘以2的幂次倍运算。
$$floor(x/2^k)=x>>k$$
对于无符号数和补码数都成立。

可以使用一点技巧来对补码数向上舍入：
$$ceil(x/2^k)=(x+(1<<k)-1)>>k$$

4.IEEE浮点数

二进制的小数位级形式如下的向量序列：
$$b_m{b}_{m-1}\cdot \cdot \cdot b_1{b}_0.b_{-1}{b}_{-2}\cdot \cdot \cdot b_{-n-1}{b}_{-n}$$
每个位表示0或1，再给每个数一个权重，则有：
$$b=\sum _{i=-n}^m{2}^i\ast b_i$$
这种定点表示法，很难有效的表示很大的数字。

IEEE浮点标准使用以下形式表达一个数：
$$V=(-1{)}^s\ast M\ast 2^E$$

• 符号(sign)， s决定这是负数(s=1)还是正数(s=0)，而对于数值0的符号位解释需要特殊处理。
• 尾数(significand)，M是一个二进制小数，范围是[1,2-e]，或者[0,1-e]。
• 阶码(exponent)，E的作用是对浮点数加权，这个权重是2的E次幂，可以是负数。

将浮点数的位表示划分为三个字段，分别对这些值进行编码：

• 一个单独的符号位s直接编码符号s
• k位的阶码字段$exp=e_{k-1}\cdot \cdot \cdot e_1{e}_0$编码阶码E。
• n位小数字段$frac=f_{n-1}\cdot \cdot \cdot f_1{f}_0$，编码尾数M，但是编码出来的值，也依赖于阶码字段的值是否等于0。

根据阶码的值，被编码的值可以分成四类(单精度为例)：

规格化的值：

当exp的位模式既不全0，也不全为1时。阶码字段被解释为以偏置形式表示的有符号整数。

比如对于单精度浮点数，其阶码位有8位，那么取值在1-254之间，偏置为127，则实际指数可取值[-126，127]。对于双精度来说，偏置为1023，实际指数取值[-1022，1023]。

小数字段被解释为小数值f，其范围[ 0 , 1 )，二进制表示为$0.f_{n-1}{f}_{n-2}\cdot \cdot \cdot f_2{f}_1{f}_0$。

尾数定义为M = 1 + f 。 也被称为隐含的以1开头的表示。即科学计数法表示。

非规格化的值：

当阶码域全为0时，所表示的数是非规格化形式的，其指数值是固定的$E=1-Bias$，对于单精度，其固定时-126，双精度固定为-1022。

尾数定义为M = f ，直接是小数字段的值，不包含隐含的开头的1。

特殊值：

即阶码全为1时，一个表示无穷值，另外一个表示Not a Number。

浮点数的值不是均匀分布的，在0附近比较稠密，向外密度逐渐降低。

浮点数的位级表达形式是有序排列的，如果按无符号数的编码形式来解释，那么有：

• 正浮点数是升序排序。
• 浮点数是降序排序。

4.1 常见的单精度和双精度浮点数

以下是非负浮点数的实例：

以下是一个实例，把整数值转变成IEEE单精度浮点数：

• 如整数12345，二进制表示成[11000000111001]。
• 将二进制小数点左移13位，创建这个数的一个规格化表示，得到$12345=1.1000000111001_2\times 2^{13}$。
• 这是一个规格化的值，可以去掉1。然后在末尾增加10个零，来构造小数字段。
• 阶码字段需要加上偏置值127+13=140，则为[10001100]。
• 加上符号位为0。

(IEEE单精度浮点数)([0][100011000][1000001110010000000000])=12345.0
1

4.2 向偶数舍入

这种摄入方式在非中间数时按四舍五入方法来取近似，但遇见中间数。

则其按舍入之后最低位为偶数的规则来进行近似！

如1.35近似为1.4，1.45近似为1.4。

这种近似方法可有效避免近似造成的统计性偏差。

必须是两个可能值的中间值才能采取这种策略。

因此，浮点数加法运算不具备结合性，乘法运算不具备交换性。

此外 ，浮点数乘法具有单调性：

对于任意的a，b，c，且它们都不为NaN，则有：
$$\begin{gathered} a\ge b且c\ge 0,则有a\ast c\ge b\ast c \\ a\ge b且c\le 0,则有a\ast c\le b\ast c \end{gathered}$$
从浮点数向整数转换可以能会溢出，精度也可能丢失。

当范围溢出时，Interl兼容处理器会有一个TMin值作为整数不确定值。

此外，Inter兼容处理器上也有一个“扩展精度”浮点形式，具有80位长，1个符号位，15个阶码位，1个整数位，63个小数位。

而且后来也出现了16位浮点数的IEEE标准。

---

---

---

（------------------完--------------------)

夜很深，但相信很多人依旧在奋斗，致敬每一个为了梦想不懈学习的人，期待日后有缘相见。