整数的表示

需了解原码、补码的计算方法，为后续内容的基础。

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 和正整数），不包含负数。

纯二进制表示

在非负数中，数字中的第 $n$ 位的大小就是 $2^{n}$。

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

$$U_{\text{decimal}} = \sum_{i=0}^{n-1} 2^{i} \cdot b_{i}$$

纯二进制表示范围

根据以上公式可知，一个 $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$

在现代 64 位计算机中，unsigned 是 32 位非负数。也可以使用 uint16_t 表示 16 位非负数、uint32_t 表示 32 位非负数、uint64_t 表示 64 位非负数。

十进制 → 二进制

将十进制字面值转化为无符号数的方法就是使用 $U_{\text{decimal}} = \sum_{i=0}^{n-1} 2^{i} \cdot b_{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_{\text{binary}} = b_{n-1} \cdots b_{1} b_{0}$，对应的十进制数为：

$$S_{\text{decimal}} = \sum_{i=0}^{n-2} 2^{i} \cdot b_{i} - 2^{n-1} \cdot b_{n-1}$$

补码的表示范围

根据以上公式可知，一个 $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$ 位补码表示中的补数定义如下：

$$x\ \text{\small 的二进制补数} = 2^n - x$$

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

比如假设给定一个十进制 $D$，首先我们可以通过除 2 取余法计算其纯二进制表示 $U_{binary} = u_{n-1} \cdots u_{1}u_{0}$，然后再用 $2^n$ 减去这个数：

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

$$S = 2^n - U = \bar{U} + 1$$

二进制 → 十进制

这里为了方便说明，以 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_{\text{decimal}} = \sum_{i=0}^{n-2} 2^{i} \cdot b_{i} - 2^{n-1} \cdot b_{n-1}$ 这个公式进行直接观察。

比如 $-73 = -128 + 55 = -128 + 32 + 16 + 4 + 2 + 1 = -2^7 + 2^5 + 2^4 + 2^2 + 2^1 + 2^0$，对应的补码为 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 位二进制数为例）：

+5 的原码是：00000101
-5 的原码是：10000101

缺点

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

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