Last updated on 2 years ago

信息的表示和处理

信息的表示和处理

编码

无符号(Unsigned)数的编码

设一个整数数据有位，我们可以将其写成位向量来表示该向量，或者将其每一位都写出来

对于向量，有：

补码(Two's-complement)数的编码

对于向量，有：

对于补码数的编码，其实就是无符号数的最高位变为负数，其余都是一样的

我们以位的无符号数与补码数为例，讨论二者的表示范围：

对于位的无符号数的范围，有：

对于位的补码数的范围，有：

对于补码数而言，负数的个数有个，非负数的个数也有个，这导致了：

其他编码方式

反码(Ones'Complement)编码

反码编码只是在补码的基础上将最高位的权重从变为，其余都跟补码一样

原码(Sign-Magnitude)编码

原码的最高位为符号位，其余位来决定该数的大小

这两种编码都有一个问题是，对于数字会有两种解释方式

在原码中被解释为，被解释为

在反码中被解释为，被解释为

实际上，浮点数的编码方式就是才有原码编码

无符号数与补码数的转换

对于补码和无符号数之间的转换，底层的位值表示是不变的，只是改变了解释这些位的方式

补码转无符号

无符号转补码

拓展一个数字的位表示

我们主要讨论从一个较小的类型转换到较大的类型

无符号的拓展

无符号的拓展被称为零拓展(zero extention)，只需要简单的在开头添加即可，其原理如下：

定义长度为的位向量和长度为的位向量，其中

此时有：

补码数的拓展

补码数的拓展被称为符号拓展(sign extention)，即在前面添加最高有效位

最高有效位为，那么添加；最高有效位为，那么添加

定义长度为的位向量和长度为的位向量，其中

我们有：

推导：

我们只需证明：，便可以说明对于任意位数的符号拓展，都是满足条件的

我们按照补码数的定义展开，有：

本质上是使用属性：

截断数字

截断无符号数

设表示位向量，为其截断为位的结果：，我们有：

本质上是对于任意的，都有：

截断补码数

设表示位向量，为其截断为位的结果：，我们有：

本质上是先将位向量截断为位，然后在从补码的角度诠释位表示

整数运算

右移方式

右移方式有两种：逻辑右移与算术右移

前者会直接补，后者会补最高有效位；如果最高有效位为，那么便补，如果最高有效位为，那么便补一

对于无符号数，右移均为逻辑右移

对于补码数，右移均为算术右移

无符号加法

设，有：

两个位的无符号数相加，其结果可能需要位来表示

若两个位的无符号数相加，如果加和会自动截断为位

无符号加法溢出的检测

设，令，当且仅当（或等价条件）成立时，发生了溢出

代码判断：

//未发生溢出时返回true，发生溢出时返回false
bool uadd_ok(unsigned x, unsigned y)
{
    unsigned sum = x + y;
    return sum >= x;
}
CPP

无符号的非

设，其位的逆元有下式给出：

求无符号的非，本质上是对于一个无符号数，找到一个使得：

因此直接在的基础上加一个使其溢出的数即可

补码加法

设，有：

对于位的补码数可表示的最小值为，可表示的最大值为

因此如果两个位的补码数相加，其结果可能需要位来表示

如果结果大于，则发生正溢出，位的值由变为，数值上相当于加和结果减去

如果结果小于，则发生负溢出，位的会溢出为，由于我们需要将该位舍去，因此数值上相当于加和结果加上

补码加法溢出的判断

设，令

当且仅当而时，发生正溢出

当且仅当而时，发生负溢出

代码判断：

//返回-1表示负溢出，1表示正溢出，0表示正常
int tadd_ok(int x, int y)
{
    int sum = 0;
    if(x < 0 && y < 0 && sum >= 0) return -1;
    else if(x > 0 && y > 0 && sum <= 0) return 1;
    else return 0;
}
CPP

该程序不能写成：

int tadd_ok(int x, int y)
{
    int sum = x + y;
    return (sum - x == y) && (sum - y == x);
}
CPP

这是因为，无论补码加法是否溢出，sum -x == y 都始终成立（补码加法是模数加法，具有循环的特性）

如果需要判断是否发生溢出，不能写成：

int tsub_ok(int x, int y)
{
    return tadd_ok(x, -y);
}
CPP

当取除以外的任何值时，都是满足条件的，但当时，此函数做出了与我们期望相反的行为

当时，该函数认为只要时就不会发生溢出，只要时就会发生溢出，但实际与此刚好相反

当时，，若，其实际计算结果为正数，但位表示却为负数，因此发生了溢出；同理，若，其实际计算结果依旧为正数，在位表示上，溢出的一位会被舍去，而符号位为，即位表示为正数，因此没有发生溢出

正确写法：

//溢出返回1，未溢出返回0
int tsub_ok(int x, int y)
{
    int sub = x - y;
    return (x > 0 && y < 0 && sub < 0) || (x < 0 && y > 0 && sub > 0);
}
CPP

补码的非

设，的补码非由下式给出：

补码的非本质上同无符号的非一样，都是找一个数使得，本质上都是模数加法的溢出

在位表示上，对于任意值，所求得的值就是的非，即

快速求补码非的办法

在的二进制表示中，设为最右边的的位置，即的位表示为（只要不为就总能找到这样的）

这个值的非的位表示为

也就等同于，将的左边所有位均取反

无符号乘法

对于，无符号乘法结果由下式给出：

两个位的数相乘，结果可能需要位才能表示，因此无符号程序会将结果截断为位

补码乘法

对于，补码乘法结果由下式给出：

其实就是将乘法结果截断为位，然后再从补码的角度解释

乘以常数

乘以 2 的次幂

我们先讨论乘以的次幂的情况

无论是无符号数还是补码数，乘以相当于将位表示左移个单位，然后再对其进行截断，即：

乘以任意常数

对于乘以任意常数的情况，我们将的二进制表示写出来：，必然会是连续的交替的情况

例如，可以写为，考虑位位值从到的一组连续的（，且二者均从开始）。（对来说，）我们可以用以下两种方式来将乘以任意常数转换成加法、减法与移位操作：

问题：如果加法、减法、移位所需的时间相同，那么当取不同值时，编译器该如何决定选择哪一种操作？

分类讨论：

如果，那么第一种只需要一次移位，第二种需要一次减法和两次移位

如果，那么第一种需要两次移位和一次加法，第二种需要两次移位和一次减法

如果，那么第二种只会需要两次移位和一次减法，第一种需要次移位和次加法

综上，我们有如下结论：

若，选第一种
若，哪种都行
若，选第二种

除以 2 的幂

取整的描述

对于除法，我们期望其结果总是舍去小数，这一点对正数和负数我们都期望是成立的

例如，我们期望：

这种舍入我们称为向零舍入，即直接舍去小数位

为了更便于描述该过程，我们需要引入两个符号：下取整与上取整

对于任意实数，我们定义生成唯一整数使得，生成唯一整数使得

例如：

生成，使得

我们发现，对于整数的向零舍入，恰好用下取整便可以描述，而对于负数的向零舍入，我们需要上取整才可以描述

无符号除法

若一个无符号数除以，则对其执行算术右移个单位，所得二进制表示便是下取整的结果

例如：，将其右移一位（除以），所得位表示为，我们发现这恰好变式下取整

对于无符号数值和整数而言，

补码除法

对于补码的除法，我们需要在右移的过程中保证符号不变，因此必须执行算术右移

我们从一个例子出发，考虑对负数直接执行算术右移的操作后，其结果如何

如果我期望将右移一位除以，那么所得位表示为

我们发现，不论是逻辑右移还是算术右移，其结果都是下取整。这对于正数是合理的，但对于负数却不是我们希望的，我们需要一种办法将下取整转换为上取整

我们利用如下等式：

例如，当时，，此时我们有，而

对于补码数和整数而言，

到此为止，我们已经讨论了除以的幂次的情况，但不幸的是，除法无法像乘法那样推广到除以任意常数。换句话说，对于任意常数，我们无法将其简单地转为除以多个的幂次相加的情况

你也许会想，任意一个数都可以分解为的幂次，并且乘法与除法都满足分配律，为什么除法不能像乘法那样分解呢？

这里的问题在于，除法会有舍入的问题（而乘法不具有这种问题），如果将其简单的分解为多个数相除，那么小数的部分将会全部被舍去，这将会导致最终的结果与我们所预期的相差过大

浮点数

表示

所有二进制小数均可以表示成以下形式：

数学定义如下：

基于此，我们给出浮点标准：

浮点数表示为：

符号 (sign) 用于决定该数为正数还是负数
- 单精度为位，双精度为位
尾数 (significand) 是一个二进制小数，范围为 (denormal) 或 (normal)
- 单精度为位，双精度为
阶码 (exponent) 用于对浮点数加权
- 单精度为位，双精度为

下面我们以单精度为例，说明的三种不同情况：

Normal

当 exp 位表示不全为零（数值为零）也不全为一（单精度为，双精度为）时，属于此种情况

此时阶码值，其中为 exp 的无符号位表示，即，而的值为（单精度为，双精度为）

此时，单精度的范围为，双精度的范围为

此时 frac 字段的位表示用于描述小数值，二进制表示为，而尾数的值为（采用此种表示可以额外获取一位的精度）

Denormal

当 exp 的位表示全为零时为此种情况，此时阶码值（这是特殊规定的，而不是），而尾数的值为（此时开头不包含隐含的）

非规格数的作用是用于表示那些非常接近的数，这被称为逐渐下溢 gradual underflow

INF & NaN

当 exp 字段全为一且 frac 字段全为零时，表示无穷大，分为正无穷大与负无穷大

当 exp 字段全为一且 frac 字段不全为零时，表示 Not a Number

范围

`Description`	`exp`	`frac`
`0`	`00...00`	`00...00`
	`00...00`	`00...01`
	`00...00`	`11...11`
	`00...01`	`00...00`
	`01...11`	`00...00`
	`11...10`	`11...11`

舍入

定义了四种舍入方式，分别如下：

向上舍入

将正数与负数均向上舍入，得到值，使得

正数	负数

向下舍入

将正数与负数均向下舍入，得到值，使得

正数	负数

向零舍入

将正数向下舍入，负数向上舍入

正数	负数

不难发现，相当于直接去掉小数位

向偶数舍入

将数字向上或向下舍入，使得最低有效位为偶数

对于十进制小数而言，小于的均向下舍入，大于的均向上舍入

对于等于的数，考虑在原先的基础上加上或减去 ，最终结果取偶数

具体来说，加上或减去，得到或，我们取偶数

对于二进制小数而言，小数点后所有小于的向下舍入，所有大于的向上舍入

对于等于的数，考虑在原先的基础上加上或减去 ，最终结果取偶数

具体来说，可以得到与，在这里取

上面的讨论均是以舍入到整数，如果是舍入到小数点后的情况，也是同理

浮点运算

我们定义浮点数加法

由于浮点数溢出和舍入，因此浮点数加法是可交换的但不可结合的，也就是只满足

例如，使用 float 计算会得到，但计算会得到

其次，除了和，其余的浮点数值均存在逆元，即

另一方面，浮点数满足单调性，即对于任意的，如果，那么有，而无符号数与补码数均不具有此属性

我们定义浮点数乘法

同样由于浮点数的舍入与溢出，乘法只具有交换性而不具有结合性，并且乘法也不具有分配性