信息的表示和处理（2）：整数表示

作者: 月月月月_bd25 | 来源:发表于2019-01-27 17:05 被阅读0次

信息的表示和处理（2）：整数表示
[2018-12-04] Basic Knowledges
信息的表示和处理（3）：整数运算
信息的表示和处理
信息的表示和处理
信息的表示和处理
信息的表示和处理
信息的表示和处理
第2章信息的表示和处理
第2章信息的表示和处理

精确定义如何编码和操作整数的数学术语：

整数数据和算术术语表

1.1 整数数据类型

32位程序上C语言整型数据类型的取值范围

64位程序上C语言整型数据类型的取值范围

唯一一个与机器相关的类型是long，其他类型的取值范围在32位机器和64位机器都一样。
所有类型的取值范围都是不对称的，负数范围比整数范围大1。

C语言标准中整型数据类型必须至少保证的取值范围

C/C++都支持有符号数和无符号数，默认是有符号数。Java只支持有符号数。

1.2 无符号数的编码

无符号数编码的定义

对向量 $\vec { x } = \left[ \begin{array} { l l l l l } { x _ { w - 1 } , } & { x _ { w - 2 } , } & { \cdots , } & { x _ { 0 } } \end{array} \right]$ ,

$B 2 U _ { w } ( \vec { x } ) \doteq \sum _ { i = 0 } ^ { w - 1 } x _ { i } 2 ^ { i }$

也就是说，一个无符号整数，等于第i位的比特值乘 $2 ^ i$ , 再将各项相加，即得整数值。
函数 $B2U_w$ 的取值范围是，[0, $2^\omega$ - 1]。每个介于这个区间的数都有唯一一个 $\omega$ 位的值编码。反过来，每个处于这个区间的位模式，都有一个大小在这个区间的整数与之对应。因此， $B2U_w$ 是一个双射。

1.3 补码编码

补码是有符号数的表示方式。字的最高有效位解释为负权。
补码的定义
- 最高有效位 $x_{\omega-1}$ 称为符号位，权重是 $-2^{\omega-1}$ 。是无符号表示中权重的负数。
- 符号位被设置为1时，值为负，设置为0时，值为非负。
$\omega$ 位补码，能表示的最小值是[10...0]，其整数值为 $T M i n _ { w } \doteq - 2 ^ { w - 1 }$ 。最大值为[01....1]，其整数值为 $\operatorname { TMax } _ { w } \doteq \sum _ { i = 0 } ^ { w - 2 } 2 ^ { i } = 2 ^ { w - 1 } - 1$ 。（实际上，按照上面的定义公式，将最小值和最大值的比特位代入公式，也可得出最小值和最大值的值）。
在取值范围内的每个补码都有一个唯一的 $\omega$ 位的补码。和无符号数一样，补码编码的函数 $B2T_\omega$ 也是一个双射。

几个重要位模式示意图

重要数字取值范围图表

补码范围不对称， $| \operatorname { TMin } | = | \operatorname { TMax } | + 1$ ,即TMin没有与之对应的正数。因为符号位设置为1 的数表示负数，而符号位为0的数表示非负数，两者各占一半。但由于全0是非负数，所以能表示的正数比负数少一个。
最大的无符号数值刚好比补码的最大值的两倍多一。 $U M a x _ { w } = 2 T M a x _ { w } + 1$
补码表示中所有表示负数的位模式在无符号表示中都变成了正数。
几乎所有机器都是以补码形式来表示有符号整数。C语言中没有要求用补码形式表示有符号整数，但是在Java中明确要求用补码表示整数，单字节数据类型称为byte。这些都是为了保证Java在任何机器上运行都能表现一致。

原码、反码、补码

有符号数的其他表示方式(1)

有符号数的其他表示方法(2)

注意区别于无符号数，上图列出的都是有符号数的表示方式。即有符号数的表示方式可以有原码、反码、补码三种，而无符号数的表示方式，按照除2取余法即可得到，不存在符号位。
原码、反码、补码之间的转换关系，简单来说，就是原码按位取反得到反码，反码最低位+1得到补码。
用原码或反码表示数字0时，都会存在正负0的问题。但是用补码表示，正负0的值都是唯一的，不存在这个问题。存在正负0的原因是符号位不同导致的。

1.4 有符号数和无符号数之间的转换

强制类型转换的结果保持位值不变，只是改变了解释这些位的方式。
处理同样字长的有符号数和无符号数之间相互转换的规则是：数值可能会改变，但是位模式不变（二进制位对应的值不变）
T2U（有符号数转无符号数）的一般行为：负数转换成了大的正数，非负数保持不变。U2T的一般行为：小的数（ $\le TMax_\omega$ ），从无符号到有符号的转换将保留数字的原值。对于大的数（ $\gt TMax_\omega$ ），数字将会被转换成一个负数值。
有符号数和无符号数的互相转换图

总结：

在范围 $0\le x\le TMax_\omega$ 内的值，T2U(x)=x, U2T(x)=x。即在这个范围内的数字有相同的无符号和补码表示。
在上述范围之外的值，转换需要加上(T2U)或者减去(U2T) $2 ^ \omega$ 。

如何从一个负数得到它的补码表示？

官方定义，补码编码的定义如下：

补码的定义
但这只是列出了从补码编码得到负数的过程，如果通过这个函数求反函数会比较困难。

民间做法：

对于非负数，其无符号数表示和补码表示相同。则按照除2取余法得到该非负数的补码表示。

对于负数，先按照非负数的做法，求得其绝对值的原码表示。然后，对原码进行取反，再加1。这时再看符号位，因为是负数，符号位必定为1，若求得补码的最高位是1，则此时得到的补码即为所求。如果此时最高位是0，说明此时求得的补码已经超出了位数的取值范围，需要扩大位数，再次执行上述原码取反加1 的过程，即可得到补码表示。

举例说明

比如需要知道-5的补码，用4位比特位表示，则按照民间做法，-5 绝对值为5，5的原码是0101，按位取反加1 得1011，此时最高位是1，即符号位为1，则1011为-5的补码。

验证：按照官方定义，补码1011对应的整数是： $-1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = -5$ 。

再比如需要知道-11的补码，如果仍用4位比特位表示，按照上述方法，绝对值原码（1011）取反加1 ，则得到的绝对值的补码是0101，符号位是0，而负数的符号位应该是1，说明超过了-11超过了4位比特位所能表示的取值范围。因此扩大到8位比特位，再求绝对值原码（0000 1011）取反加1 得 1111 0101。此时最高符号位是1，则1111 0101是-11 的补码。

验证：按照官方定义计算补码 1111 0101 对应的整数，得-128+64+32+16+4+1=-11。

1.5 C语言中的有符号数和无符号数

当声明一个无符号常量时，需要在数字后面加上后缀字符'U'或'u'，否则就会被认为是有符号的。
当执行一个运算时，一个运算数是有符号的，另一个运算数是无符号的时候，会隐式地将有符号数强转成无符号数。对于<、>这样的关系运算来说就会有问题，而对于标准算术运算来说无什么差异。关系运算示例如下所示：
C语言升级规则的效果

1.6 扩展一个数字的位表示

无符号数的零扩展：将无符号数转换为一个更大的数据类型，只需简单地在表示的开头添加0，这种运算叫零扩展。
补码数的符号扩展：将补码数字转换为一个更大的数据类型，只需要在开头添加最高有效位的值，这种运输叫符号扩展。其本质是，加上一个权值为 $-2^\omega$ 的位（即加上一个符号位），和将权值为 $-2^{\omega-1}$ 的位转换为一个权值为 $2^{\omega-1}$ 的位（即将原来符号位的负权消除，但保留了该位所表示的数值），这两项运算的综合结果保持了原始的数值。（即 $-2^{\omega-1} = -2^\omega + 2^{\omega-1}$ ）。
一个数据的类型大小转换，以及有符号数和无符号数的转换，它们的相对顺序会影响程序的行为。在C语言标准中，需要先改变大小，再完成从有符号数和无符号数的转换。

1.7 截断数字

截断无符号数：将一个 $\omega$ 位的数截断为一个k位的数（ $\omega \ge k$ ），会将 $\omega - k$ 位丢弃，得到截断后的k位无符号数。
截断补码数值：和截断无符号数类似，截断后得到k位的无符号数，然后将最高位转换为符号位，即得到截断补码的值。

两者都采用了同样的属性：对于任何的 $i\ge k, 2^i mod 2^k = 0$ 。

1.8 有符号数和无符号数的建议

有符号数和无符号数在程序中的转换可能会出现难以发现的错误。避免错误的一种方法是不使用无符号数。
除C语言外很少有语言支持无符号整数。在Java中，支持有符号整数，且要求以补码运算实现，>> 被定义为算术右移，>>>被定义为逻辑右移。
无符号数的应用场景：用于把字看作是位的集合而没有任何数字意义；用于系统中的内存地址；可用于实现模运算和多精度运算的数学包。

其中细微的错误可参照习题2.25和2.26，

信息的表示和处理（2）：整数表示
精确定义如何编码和操作整数的数学术语： 1.1 整数数据类型唯一一个与机器相关的类型是long，其他类型的取值范...
[2018-12-04] Basic Knowledges
https://zhuanlan.zhihu.com/p/51183862 信息的表示和处理计算机如何表示整数：...
信息的表示和处理（3）：整数运算
1.1 无符号加法无符号加法定义正常情况下, x+y的值保持不变。溢出情况下，x+y的值是该和减去的结果。 ...
信息的表示和处理
比特及位级运算现代计算机存储和处理信息以二进制信号表示，一个二进制数称为位。大多数的计算机使用8位，或者字节，作...
信息的表示和处理
主要研究三种数字表示1、无符号编码2、补码编码3、浮点数编码一些基本概念整数表示相对小的数值范围，但是一个精确...
信息的表示和处理
在阅读《深入理解计算机系统》的过程之中，有一些知识点是我觉得有必要记录下来的，在这里进行一定的总结。文本数据比二...
信息的表示和处理
信息的存储字数据大小计算机中，字长指的是指针数据标称大小，虚拟地址以字来进行编码的，所以字长w位的机器，可以表...
信息的表示和处理
现代计算机存储和处理的信息以二值信号表示。这些微不足道的二进制数字，或者称为位 (bit), 形成了数字革命的基础...
第2章信息的表示和处理
2.16 2.17 2.18 A : 736 B : -88 C : 40 D : 48 E : 120 F : ...
第2章信息的表示和处理
无符号（unsigned）编号基于传统的二进制表示法，表示大于或等于零的数字。补码（two‘s-comple...