计算机中整数的表示和运算

作者: 兴尽而来 | 来源:发表于2020-07-13 21:56 被阅读0次

我们知道，计算机系统中所有信息——包括磁盘文件、内存中的程序、内存中存放的用户数据以及网络上传送的数据，都是由一串比特表示的。区分不同数据对象的唯一方法是我们读到这些数据对象时的上下文。比如，在不同的上下文中，一个同样的字节序列可能表示一个整数、浮点数、字符串或机器指令。

本文将从二进制编码的角度介绍计算机系统中整数的表示方法，同时会结合 C 语言，介绍不同类型的整型数据进行类型转换、移位运算、求反运算时在位级层面的行为。

整数表示

整数主要有两种编码方式。一种只能用来表示非负数，另一种能够表示负数、零和正数，对应着 C 语言中的无符号数和有符号数。而 Java 只支持有符号数。

无符号编码

无符号编码基于常规的二进制表示法。将一个 ω 位的位向量 $\vec x$ 看作二进制数，就得到了 $\vec x$ 的无符号表示。此处使用符号 $B2U_ω$ 表示将 ω 位的位向量根据无符号编码映射到非负整数，有：
$B2U_ω(\vec x) = B2U_ω([x_{ω-1},x_{ω-2},...,x_0]) = \sum_{i=0}^{ω-1}x_i2^i$
例如：
$B2U_4([1101]) = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 13$
根据以上公式可知 ω 位无符号编码的值范围为 $[0,2^ω-1]$ 。

补码编码

很多情况下我们需要使用负数值，最常见的有符号数的计算机表示方式就是补码（two's complement）形式。补码编码中，将最高位解释为负权值。此处使用符号 $B2T_ω$ 表示将 ω 位的位向量 $\vec x$ 根据补码编码映射到整数，有：
$B2T_ω(\vec x) = B2T_ω([x_{ω-1},x_{ω-2},...,x_0]) = -x_{ω-1}2^{ω-1} + \sum_{i=0}^{ω-2}x_i2^i$
例如：
$B2T_4([1101]) = -1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = -3$
ω 位补码的值范围为 $[-2^{ω-1},2^{ω-1}-1]$ 。

为什么使用补码表示有符号数

现在几乎所有现代机器都使用补码，一个主要原因是用补码来表示负数，使得我们的整数相加变得很容易，不需要做任何特殊处理，只是把它当成普通的二进制相加，就能得到正确的结果，通过硬件电路实现最为简单且高效。我们以 4 位的整数加法为例说明以下，如 -5 + 1 = -4，-5 + 6 = 1。

补码加法

有符号数的其它编码方式

反码（Ones' complement）
除了最高有效位的权是 $-(2^{ω-1} - 1)$ 而不是 $-2^{ω-1}$ ，它和补码是一样的：
$B2O_ω(\vec x) = -x_{ω-1}(2^{ω-1} - 1) + \sum_{i=0}^{ω-2}x_i2^i$
原码（Sign-Magnitude）
最高有效位是符号位，用来确定剩下的位应该取负权还是正权：
$B2S_ω(\vec x) = (-1)^{x_{ω-1}} \cdot \sum_{i=0}^{ω-2}x_i2^i$

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

C 语言中的转换规则

C 语言中允许在不同的数字数据类型之间做强制类型转换，包括有符号数和无符号数之间。虽然 C 标准没有指定有符号数要使用某种表示，也没有精确规定有符号数和无符号数之间如何进行转换，但几乎所有机器都使用补码，同时大多数系统遵循的同等字长有符号数和无符号数之间的转换规则是：

数值可能改变，底层位模式不变。

我们使用一个例子进行说明：

// 根据补码编码规则，-1 的位表示为 0xFFFFFFFF
int x = -1; 
// 强制类型转换并不会改变底层位模式，所以 u 的位表示同样是 0xFFFFFFFF
// 根据无符号编码可知 u 的值为 4,294,967,295
unsigned u = (unsigned)i;

类型转换可能导致的问题

什么是 C 语言的算术转换?

如果某个运算符的多个操作数属于不同的类型，那除非操作数转换为相同的类型，否则操作无法进行。一般转换规则是：unsigned long > long > unsigned int > int。如果某个操作数类型在上面这个列表中排名较低，那它将首先转换为另一个操作数的类型，然后执行操作。

C 语言中有符号数和无符号数之间的转换规则加上它的算术转换的性质可能会导致一些奇特的行为。如果一个表达式中既有无符号数也有有符号数，那么有符号数会被隐式转换为无符号数，这种行为对算术运算影响可能并不大，但对于 >、< 这些关系运算符来说，会导致一些非直观的结果，看一些例子：

表达式	类型	结果
-1 < 0U	无符号	0
2147483647U > -2147483647 - 1	无符号	0
2147483647 < (int)2147483648U	有符号	0

C 语言中 Tmin 的写法

上一个小节的例子中，我们使用 -2147483647 - 1 来表示 32 位补码能表示的最小值，再看一下 C 标准库头文件 limit.h 文件中定义的 $Tmin_{32}$ 和 $Tmax_{32}$ ：

#define INT_MAX = 2147483647
#define INT_MIN = -INT_MAX - 1

为什么不用 -2147483648 或 0xFFFFFFFF 来表示 Tmin 呢？

这和 C 语言中对整型常量的实际类型的认定是有关的。整型常量的实际类型取决于长度、基数、后缀字母和 C 语言实现的确定的类型的表示精度。具体的规则如下表所示：

常量形式	C89	C99
十进制	int long unsigned long	int long long long
八进制十六进制	int unsigned long unsigned long	int unsigned long unsigned long long longg unsigned long long

常量的数据类型是从上面表格里选择第一个最合适（能表示常量而不溢出的）的类型。另外，C 标准中规定整型常量以数字开头，前面可以包含指定基数的前缀。也就是说如果不发生溢出，整型常量的值总是非负数。如果前面出现负号，则是对整型常量使用的一元运算符，而不是整型常量的一部分。

根据以上规则，以32 位机器典型的数据类型精度为例，我们来看-2147483648 和 0xFFFFFFFF 实际类型分别是什么?

2147483648 超出了 int 和 long 类型所能容纳的最大值，所以用 unsigned long 类型来容纳，前面的负号作为运算符对这个无符号数求反，结果依然是 unsigned long 类型。而 0xFFFFFFFF 则会使用 unsigned 类型容纳，求反后依然是 unsigned 类型。这也就是为什么 C 语言中定义 Tmin 不用不用 -2147483648 或 0xFFFFFFFF 来表示的原因。

数字的扩展和截断

当不同字长的数据类型之间进行转换时，就会涉及到数字的扩展和截断，只需要遵守以下规则：

无符号数进行零扩展
有符号数进行符号扩展
数字截断就是将高位多余的位数直接丢弃
C 标准中规定，类型转换时首先进行扩展与截断，再进行有符号和无符号之间的转换

整数运算

移位运算

左移

C 表达式x << k表示 x 向左移动 k 位，丢弃最高的 k 位，并在右端补 k 个 0.

右移

C 表达式x >> k表示 x 向右移动 k 位，一般机器支持两种形式的右移：

逻辑右移：在左端补 k 个 0

算数右移：在左端补 k 个符号位

对于无符号数使用逻辑右移。虽然 C 标准没有明确定义对于有符号数使用哪种类型的右移，但几乎所有编译器/机器都是用算数右移。
Java 对于如何右移进行了明确规定，表达式x >> k进行算术右移；表达式x >>> k进行逻辑右移。

移动 k 位，k 很大
对于一个 ω 位组成的数据类型，如果要移动 k ≥ ω 位会得到什么结果？

C 标准没有明确定义，许多机器上，当移动一个 ω 位的值时，移位指令仅会考虑位移量的低 $log_2ω$ 位，因此实际的移位量就是通过计算 k mod ω 得出来的，但这种行为对于 C 程序而言是没有保证的。

Java 中明确要求位移量按照上述取模的方法来计算。

求反运算

无符号数求反
对满足 $0 ≤ x< 2^ω$ 的任意 x，其 ω 位的无符号逆元由下式给出（ $-^u_ω$ 表示对无符号数取反）：
$-^u_ωx=\left\{\begin{array}\\x，&x = 0\\2^ω-x，&x>0\end{array}\right.$
补码的非
对满足 $-2^{ω-1}≤x<2^{ω-1}-1$ 的任意 x，其 ω 位的补码的非由下式给出（ $-^t_ω$ 表示对补码取反）：
$-^t_ωx=\left\{\begin{array}\\-2^{ω-1}，&x = -2^{ω-1}\\-x，&x>-2^{ω-1}\end{array}\right.$

补码的非的位级表示
计算一个位级表示的补码有几种更简便的方法：

对每一位求补，再对结果加1。C 语言中，对任意整数 x，算数表达式-x和~x+1得到的结果是一样的。

对从右到左的第一个 1 的左边的所有位取反。

最后

本篇文章主要主要是对整数在计算机中的存在形式以及一些类型转换和运算中的行为方式进行了总结，了解这些也是为了在写程序过程中做到有的放矢，避免一些由于数据类型导致的 bug 或者能够从位级行为上理解这些 bug 是如何产生的从而进行修复。之后我还会对浮点数、字符、字符串进行类似的总结，彻底理清楚计算机中信息的编码表示。

当然，本文没有涉及到整数加减乘除等运算的数学原理和位级行为，总体来说，计算机执行的整数运算是一种模运算形式。表示数字的有限字长限制了数据可能的值的取值范围，结果可能溢出。另外整数运算中，无论运算数是以无符号数还是补码形式表示的，都有完全一样或非常类似的位级行为。想要了解更多细节和原理，可以查阅《深入理解计算机系统》第三章节的内容。