进位计数制

简称 进制，X 进制表示逢 X 进 1。进位之后，原来位置上的符号又变成了初始符号。

以十进制为例，9 + 1 会发生进位，结果为 10，原始位置的符号又变成了 0，而 0 是 X 进制中的 X 个有序符号的第一个。

进位计数法实现了用有限的符号来表示无限的数字，它是相对于无进制的计数方法而言的。

无进制的计数方法有结绳记事、唱票的“正”字计数法等。

X 进制表示每位可以使用 X 个字符，这个 X 就是 基数，例如十进制用 0 ~ 9 这九个符号来表示。

十六进制用 0 ~ 9, A, B, C, D, E, F 这十六个符号来表示，而二进制只需要 0 和 1 这两个符号来表示。

计数符号本身没有特别含义，只是我们习惯了十进制计数法，所以 0 ~ 9 才表示我们以为的那个数字。

数的几个基本概念

以十进制数 374 为例，它实际上可拆分成

数码：即每个位置可用的计数符号，例如十进制的数码就是0,1,2,3,4,5,6,7,8,9

位数：进制计数法不同数码在不同位置上的含义不同，例如 4 在第 0 位上，3 在第 2 位上

基数：每一位上可用的符号个数，例如十进制每位可用的符号有 10 个，基数为 10；X 进制的基数就是 X

位权：每一位上的单位 1 表示的实际大小，例如 3 所在的位上 1 表示的实际上是 10^{2；X 进制第 i 位（i=0,1,...）的位权是 X}i

一些特殊的进制

除了二进制、八进制、十进制和十六进制外，生活中的许多计数法都可以看做不同的进制：

• 秒针和分针每过 60 下进一位变成一分或者一个小时，时针每转两圈进位变成一天
• 周数每过 7 天又会重新开始循环，但是本年的已过周数会加 1
• 将一个物体旋转 360 度后所在的位置跟原来一模一样
• ……

进制的另一个特点是，在不考虑进位的情况下，一个数减去一个数必然可以通过它加上另一个数实现，例如：

• 将指向 15 分的分针正拨 15 下和倒拨 45 下都会指向 30 分（60 为一个周期）
• 周三这天往后数三天和往前数四天都是周六（7 为一个周期）
• ……

在上面的例子中，60 是一种特殊的进制，因为并没有设计出 60 分符号。但是如果我们将 0 ~ 59 这 60 个数看做是独立的符号，它也是一个完备的 60 进制计数系统，即时我们在用十进制表示它，例如 00:59 + 00:02 = 01:01。

原数和补数

我们约定了一个周期比如 60，现在考虑 0 ~ 59 这 60 个数的加减法运算。

如果两个数的和大于等于 60，则发生进位，减掉 60 可得到忽略进位后的结果，例如

• 15 + 30 => 45
• 15 + 45 => 00
• 30 + 40 => 10

如果两个数的差小于 0，则发生借位，加上 60 可得到忽略借位后的结果，例如

• 45 - 10 => 30
• 10 - 20 => 50
• 20 - 20 => 00

对于 0 ~ 59 中的某一个数 x，总能找到一组 a, b 使得 x + a = x - b，跟上面拨表针的例子类似。

这样，我们可以将 x - b 转化为求 x + a，不难看出 a + b = T。

在约定的周期 T 下，假设 a + b = T，则 a 和 b 互补，假设 a 是 原数，b 就是 补数，T 也叫做 模。

对模 T 内的数的减法运算，可以转化为这个数的补数的加法运算，例如

• 15 - 3 = 15 + 57 = 12
• 15 - 20 = 15 + 40 = 5
• 15 - 15 = 15 + 45 = 0

上述特点看起来没啥实用性，但是用来理解理解计算机中的 补码 还是很有帮助的。

补数在计算机中的应用

字节 是计算机存储和传输数据的基本单位，1 byte = 8 bits。

一个字节可以转换为一个数，有符号时是 -128 ~ 127，无符号时是 0 ~ 255。

以有符号 byte 类型为例，计算机用 0000 0001 来存储 1 很容易理解，那么计算机怎么存储 -1 呢？

有符号时最高位为 1 表示负数，那么 -1 的存储格式是 1000 0001 吗？

因为符号位是我们认为规定的，计算机可不知道什么是符号，基于上面假设我们计算 1 + (-1)：

0000 0001 + 1000 0001 = 1000 0010 => -2 显然不对

我们期望的是

0000 0001 + xxxx xxxx = 0000 0000

用 0000 0000 来表示 0 是一个易于理解的前提，然而事实上，考虑有符号时，1000 0000 也可用来表示 0。因为符号是人为规定的，所以计算机可不觉得 0000 0000 和 1000 0000 是相等的。

另一个事实：计算机只能计算加法，在计算单个字节数值的加法时溢出的进位会被直接舍弃掉，例如

• 1111 1111 + 0000 0001 => 1 0000 0000 => 0000 0000

于是我们发现，当 xxxx xxxx 等于 1111 1111 时，它加上 1 等于 0，不难假设，-1 可以用 1111 1111 来表示。

进一步可推断，对于任意一个正数 0xxxx xxxx 我们都能在一个字节内找到它的相反数表示。

原数和相反数是通过舍弃溢出的进位来实现相加等于零的，这样我们就能直接从原数推断出其相反数的表示

二进制原数的相反数 = 1 0000 0000 - 二进制原数

根据二进制的特点

1111 1111 - 二进制数 = 这个二进制数的所有位取反

所以

二进制原数的相反数 = 二进制原数按位取反 + 1

这样计算减去某个二进制数，可以转化为计算加上这个这个二进制数的相反数。

所以得出结论：

• 计算机中的 1111 1111 表示 -1，而 0000 0001 表示 1
• -1 和 1 是相反数，而 1111 1111 和 0000 0001 是模为 1 0000 0000 下的互补数

此外，按照符号位的约定，0000 0000 和 1000 0000 都应该用来表示 0，但这会在计算机中引起不一致性，因为计算机会将它们看做两个不同的东西。

按照互补数和相反数的转换关系，例如我们计算 -127 - 1：

对 127 的二进制表示按位取反再加 1 得到 -127 的表示：1000 0001
-1 的二进制表示：1111 1111
故而计算结果为 1000 0001 + 1111 1111 => 1 1000 0000 => 1000 000

这里我们发现，我们以为 1000 0000 应该也可以表示 0，但是实际上它表示的是 -128。

所以对于有符号的 byte 类型：

• 0000 0000 ~ 0111 1111 表示 0 ~ 127
• 1000 0000 表示 -128
• 1000 0001 ~ 1111 1111 表示 -127 ~ -1
• 整个有符号 byte 类型能表示的数是 -128 ~ 127

总结一下，二进制补数可以将减法运算转化为加法运算，它建立了十进制数与二进制的映射，这种映射并不完全等价于我们通常学习的进制转换方式（正数一致，负数不一致），通过这种转换，计算机能够通过仅计算加法来计算我们假设的减法表达式，而且事实上，计算机只能计算加法。