整数的表示

复习提示（高优先级）：重点掌握无符号整数与补码的位权、表示范围、相互转换和溢出判断。

本章中的补码、有符号数和无符号数是组成原理的基础，必须完全掌握，也是后续讨论运算器、指令和类型转换的共同基础。

BCD 码

BCD（Binary-Coded Decimal）码是一种 二进制编码方法，用于表示 十进制数字。每个十进制数字（0-9）都使用 四位二进制数字 表示。

BCD 码的基本思路是 单独表示每个十进制数字的二进制值，而不是像传统的二进制数系统那样对整个数字进行编码。例如，在传统的二进制编码中，数字"19"会表示为 10011，但在 BCD 中，它被表示为两个独立的数字：“0001”（对应于 1）和“1001”（对应于 9），因此整个表示为“0001 1001”。

0 - 0000    1 - 0001    2 - 0010
3 - 0011    4 - 0100    5 - 0101
6 - 0110    7 - 0111    8 - 1000
9 - 1001

BCD 编码在某些应用中是很有用的，特别是在需要与 十进制界面 进行交互的地方，如 数字显示 或某些早期的计算机系统。尽管它不如 纯二进制编码 效率高，但它简化了与十进制数据的转换过程。

整数的表示

在介绍整数的不同表示之前，我们首先要定义清楚不同的名词，否则会造成极大的概念混淆。

在日常生活中，我们使用十进制表示数字，并通过符号（如 + 和 -）表示正负。这种用十进制表达的数字也叫做 字面值。

而计算机以二进制形式存储数据，补码、原码、无符号数 等只是 对二进制位的一种解释方式，它们决定了同一组二进制位所代表的实际数值。

主流通用计算机使用补码而不是原码存储有符号整数，具体原因后面会谈到。对于计算机中存储的数字来说，它的二进制可以按 有符号数（signed）或者 无符号数（unsigned）解释；同一组二进制位本身没有类型，只有在按某种方式解释时才具有相应数值。

无符号数

无符号数（unsigned number）是计算机中一种整数类型，只能表示 非负数（包括 0 和正整数），不包含负数。

纯二进制表示

在非负数中，数字中的第 $i$ 位的大小就是 $2^i$ ，也就是从最低位起第 $i$ 位的位权为 $2^i$ 。

对于一个 $n$ 位 无符号数 $U$ ，假设它的第 $i$ 位表示为 $b_i$ ，则该数字的二进制表示为 $U_{binary}=b_{n-1}\cdots b_1b_0$ ，对应的十进制数为：

U=\sum_{i=0}^{n-1}b_i2^i,\qquad b_i\in\{0,1\}

纯二进制表示范围

根据以上公式可知，一个 $n$ 位纯二进制表示的：

最小值： $0$ ；
最大值： $2^n-1$ ；
表示范围： $[0,2^n-1]$ 。

注意：无符号数就是没有符号的二进制表示，它不像 有符号数的表示那样有“补码”这个专有名词。一般可以叫它 纯二进制或 无符号数二进制表示。

二进制 → 十进制

这里为了方便说明如何将 unsigned 转化为 十进制字面值，采用 8 位 无符号数 进行说明，其中每一位表示的实际大小如下表所示：

数位	第 7 位	第 6 位	第 5 位	第 4 位	第 3 位	第 2 位	第 1 位	第 0 位
位权	$2^7=128$	$2^6=64$	$2^5=32$	$2^4=16$	$2^3=8$	$2^2=4$	$2^1=2$	$2^0=1$

10000001 对应的值为 $128+1=129$ ；
10001001 对应的值为 $128+8+1=137$ ；
01000001 对应的值为 $64+1=65$ 。

在 C 语言中，unsigned int 的具体位宽由实现决定，常见实现为 32 位；实现提供相应类型时，可用 uint16_t、uint32_t、uint64_t 明确指定 16、32、64 位无符号整数。

十进制 → 二进制

将 十进制字面值转化为 无符号数的方法，就是使用 $U=\sum_{i=0}^{n-1}b_i2^i$ 进行反向转换。

如果数字不太复杂，可以利用直觉直接观察，将一个数字转化为若干个 2 的 $n$ 次方之和（1，2，4，8，……）。比如 $73=64+8+1=2^6+2^3+2^0$ ，如果该数字为 8 位，那么对应的二进制就是 01001001。

第二种方法稍微麻烦一点，就是充当人脑计算机，采用 除 2 取余法逐步计算余数：

73 ÷ 2 = 36 ... 1
36 ÷ 2 = 18 ... 0
18 ÷ 2 = 9  ... 0
9 ÷ 2 = 4   ... 1
4 ÷ 2 = 2   ... 0
2 ÷ 2 = 1   ... 0
1 ÷ 2 = 0   ... 1

接下来将余数进行逆序重排得到二进制数：1001001，因为是 8 位数，所以在剩下的高位全部填上 0，得到结果 01001001。

总结两种转换方式如下图：

有符号数

在程序中使用 short、int、long 定义的整形变量就是 有符号数（signed），有符号数使用 补码（Two’s complement） 进行表示。

补码表示

有符号数使用的补码与 无符号数使用的 纯二进制表示方式基本相同，除了最高位。对于一个 $n$ 位补码，其最高位为 $-2^{n-1}$ ，是一个负数，而不是 $2^{n-1}$ 。

对于一个 $n$ 位 有符号数 $S$ ，假设它的第 $i$ 位表示为 $b_i$ ，则该数字的二进制表示为 $S_{binary}=b_{n-1}\cdots b_1b_0$ ，对应的十进制数为：

S=-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i

补码的表示范围

根据以上公式可知，一个 $n$ 位补码的：

最小值（最负数）： $-2^{n-1}$ ；
最大值（最正数）： $2^{n-1}-1$ ；
表示范围： $[-2^{n-1},2^{n-1}-1]$ 。

补码的命名

那么补码的命名为什么叫 Two’s Complement 呢？

对于表示范围内的正数，补码和纯二进制表示的二进制表示是相同的；但是对于负数，两者的二进制表示不同，这也是它名称的来源。

Two’s Complement 中的 Two 强调二进制系统；比如十进制中有 10’s complement（十的补码），那么在二进制中自然就是 2’s complement。

Complement 指补数的数学概念。在数学中，一个数加上 它的补数等于某个基数的幂。比如对于数字 $x$ ，其在二进制 $n$ 位补码表示中的补数定义如下：

2^n-x

所以如果给定了一个 十进制字面值，我们可以先计算其 纯二进制表示，再进行二进制减法，将 2n 减去这个数得到相应的 补码表示。

比如假设给定一个十进制数 $-U$ ，首先可以通过 除 2 取余法计算其绝对值 $U$ 的 纯二进制表示 $u_{n-1}\cdots u_1u_0$ ，然后再用 $2^n$ 减去这个数：

以上二进制减法等同于对 $U$ 进行 取反加一运算，即 $-U$ 的 $n$ 位补码 $S$ 可以被表示为：

S=2^n-U=\overline{U}+1\pmod{2^n}

二进制 → 十进制

这里为了方便说明，以 8 位补码为例说一下如何将 补码表示的二进制 转化为实际十进制数字。

首先，8 位补码中的每一位的大小为：

数位	第 7 位	第 6 位	第 5 位	第 4 位	第 3 位	第 2 位	第 1 位	第 0 位
补码位权	$-2^7=-128$	$2^6=64$	$2^5=32$	$2^4=16$	$2^3=8$	$2^2=4$	$2^1=2$	$2^0=1$

例子：

10000001 对应的值为 $-128+1=-127$ ；
10001001 对应的值为 $-128+8+1=-119$ ；
01000001 对应的值为 $64+1=65$ 。

以 8 位二进制数为例：

对于正数，例如 +5，其二进制表示为 00000101，补码也是 00000101。
对于负数，例如 -5，首先写出 5 的二进制表示：00000101。
- 按位取反得到：11111010
- 加 1 得到：11111011
- 所以，-5 的补码是 11111011。

十进制 → 二进制

这里仅讨论如何将一个 十进制负数 转化为 补码二进制，因为对于非负数，补码的二进制表示和 纯二进制 相同。

一种比较简单的转换方法，就是基于 $S=-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i$ 这个公式进行直接观察。

例如 $-73=-128+55=-2^7+2^5+2^4+2^2+2^1+2^0$ ，对应的 8 位补码为 1011 0111。

另一种就是先计算该数字绝对值的 纯二进制表示，再将其通过 取反加一的方式转化为补码。

比如通过第二种方式将 -73 转为补码：

-73 是负数，其绝对值为 73。
通过除 2 取余法得到其 无符号表示 为 0100 1001。
取反：1011 0110。
加一：1011 0111。

结果为 1011 0111。

补码的优点

使用补码可以使得 加法、减法和负数的表示 变得简单和统一。比如给定两个数字 A 和 B，我们想要计算 C = A + B。A + B 由硬件加法器得到的二进制结果可以直接作为 C 的二进制表示。

补码的设计使得负数的加法变得简单。当使用补码表示时，可以直接将两个数相加，即使其中一个数是负数，而不需要进行任何特殊处理。这简化了计算机硬件的设计。

原码

复习提示（低优先级）：原码主要用于与补码比较其编码特点及运算差异。

原码（Sign-Magnitude） 是一种简单的方式来表示二进制中的 有符号整数。在这种表示法中，数字的 最高位（最左边的位）用于表示符号，其余的位表示数字的大小。通常，符号位为 0 表示正数，而 1 表示负数。

表示方法

原码的表示方法：

正数的原码：最高位 为 0，其余位表示这个数的绝对值的二进制形式。
负数的原码：最高位 为 1，其余位表示这个数的绝对值的二进制形式。
零的原码：符号位可以是 0（表示 +0）或 1（表示 -0），但在实际应用中，通常只使用一个零，即符号位为 0。

举例（以 8 位二进制数为例）：

+25 的原码是：0 0011001
-25 的原码是：1 0011001

缺点

存在正零和负零的表示。
在进行算术运算时，正数和负数需要不同的处理，这使得硬件设计变得复杂。

由于上述的缺点，原码并不是计算机中最常用的表示法。在现代计算机中，补码是更常用的方式来表示 有符号整数，因为它简化了算术运算的处理，并且没有 +0 和 -0 的冗余表示。

反码

反码（One's Complement） 也是一种有符号整数编码。对 (n) 位正数，反码与原码、补码的位模式相同；对负数 (-x)（(x>0)），把 (+x) 的 (n) 位二进制表示逐位取反即可：

\operatorname{code}_{\text{反}}(-x) =2^n-1-x =\overline{\operatorname{code}_{\text{反}}(+x)}

例如，8 位的 (+25) 为 00011001，则 (-25) 的反码为 11100110。反码的范围为 $\left[-(2^{n-1}-1),,2^{n-1}-1\right]$ ，因此同样存在 00000000（+0）和 11111111（−0）两个零。

反码做加法时，若最高位产生了进位，不能简单丢弃，而要把这个进位加回最低位，称为 循环进位（end-around carry）。它比原码更容易复用加法器，但“双零”和循环进位仍增加了处理复杂度，因此主流通用计算机最终采用补码。

原码、反码与补码对比

以下均以 (n) 位编码为例，正数的三种表示相同；区别主要发生在负数与零：

比较项	原码（Sign-Magnitude）	反码（One's Complement）	补码（Two's Complement）
(-x) 的编码	符号位为 1，其余位写 (x) 的绝对值	对 (+x) 的全部位逐位取反	对 (+x) 逐位取反后加 1
(-25) 的 8 位编码	`10011001`	`11100110`	`11100111`
表示范围	$-(2^{n-1}-1)$ 到 $2^{n-1}-1$	$-(2^{n-1}-1)$ 到 $2^{n-1}-1$	$-2^{n-1}$ 到 $2^{n-1}-1$
零的编码	+0 与 −0 两种	+0 与 −0 两种	只有一个 0
加减运算	需先判断符号和绝对值大小	需处理循环进位	可统一为模 $2^n$ 的加法

易错点：11111111 在 8 位反码中表示 −0，在 8 位补码中表示 (-1)；同一串二进制位的数值必须先说明采用哪一种编码。