进位制

进位制，又称 进位系统（carry system）、进制系统、位置记法（positional notation）、位值记数法（place-value notation）、位置数值系统（positional numeral system），是一种能用有限种符号表示所有自然数的数字系统．一种进位制可以使用的符号数目称为 基数（radix）或 底数（base），基数为 $n$ 的进位制称为 $n$ 进制（），例如我们最常用的十进制，通常只使用 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 这十个符号来记数．进位指的是「当一个数字的某一位达到基数时，将其置为 0 并使高一位的数加一」的操作．

一般地，我们常将一个 $n$ 进制的数记作 $(a_k\cdots a_1{a}_0{)}_n$、$(a_k\cdots a_1{a}_0{)}_{(n)}$、${a_k\cdots a_1{a}_0}_{(n)}$、${a_k\cdots a_1{a}_0}_n$ 等．若基数隐含在上下文中我们也可以省略下标．注意此处的 $a_k\cdots a_1{a}_0$ 并不是 $k+1$ 个数的乘积，而是一串序列．

对于 $k$ 进制数 $a_n\cdots a_1{a}_0$，其表示的值为 $a_n{k}^n+\cdots +a_1{k}^1+a_0{k}^0=\sum _{i=0}^n{a}_i{k}^i$；对一个数 $m$，设其 $k$ 进制下的表示为 $a_n\cdots a_1{a}_0$，则有：

其中 $f(x)=\lfloor x\rfloor$．

数 $n$ 在 $k$ 进制下表示的长度为 $\lceil {\log }_k(n+1)\rceil$．

我们一般通过添加小数点「$.$」来表示小数¹、添加负号「$-$」来表示负数、在小数末尾的一段上添加上划线表示无限循环小数等．为了方便阅读，我们可以每隔若干数位添加间隔符号（如空格、$,$、' 等），如 $12345$ 表示 $12345$．

在计算机中，比较常用的进位制有二进制、八进制和十六进制．

不同进位制间的转换

十进制转其他进制

这里以二进制为例来演示，其他进制的原理与其类似．

整数部分，把十进制数不断执行除 $2$ 操作，直至商数为 $0$，之后从下到上，取所有余数的数字，即为二进制的整数部分数字．小数部分，则用其乘 $2$，取其整数部分的结果，再用计算后的小数部分依此重复计算，算到小数部分全为 $0$ 为止，之后从上到下，取所有计算后整数部分的数字，即为二进制的小数部分数字．

例子

将 $35.25$ 转化为二进制数．

整数部分：

小数部分：

即 $35.25=(100011.01{)}_2$．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <algorithm>
#include <string>

// only non-negative
// 2 <= base && base <= 36
std::string from_dec(int x, int base) {
  if (x == 0) return "0";
  std::string res;
  while (x) {
    int r = x % base;
    x /= base;

    // 写法 1
    res.push_back(r < 10 ? '0' + r : 'A' + r - 10);
    // 写法 2
    // const static std::string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // res.push_back(digits[r]);
  }
  std::reverse(res.begin(), res.end());
  return res;
}

其他进制转十进制

还是以二进制为例．二进制数转换为十进制数，只需将每个位的值，乘以 $2^i$ 次即可，其中 $i$ 为当前位的位数，个位的位数为 $0$．

例子

将 $(11010.01{)}_2$ 转换为十进制数．

即 $(11010.01{)}_2=(26.25{)}_{10}$．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <cctype>
#include <string>

// only non-negative
// 2 <= base && base <= 36
int to_dec(std::string const& s, int base) {
  int res = 0;
  for (char c : s) {
    res *= base;
    if (isdigit(c))
      res += c - '0';
    else if (isupper(c))
      res += c - 'A' + 10;
    else if (islower(c))
      res += c - 'a' + 10;
  }
  return res;
}

二进制/八进制/十六进制间的相互转换

一个八进制位可以用 3 个二进制位来表示（因为 $2^3=8$），一个十六进制位可以用 4 个二进制位来表示（$2^4=16$），反之同理．

补数法

另请参阅：反码与补码

补数法（method of complements）是用正数表示负数，使得可以用和正数加法相同的算法/电路/机械结构来计算减法的方法．补数法广泛用于计算器和计算机的设计中，用以简化结构．

对 $b$ 进制下 $n$ 位数 $a$，其 数基补数（radix complement，称为 $b$ 的补数）是 $b^n-a$，其 缩减数基补数（diminished radix complement，称为 $b-1$ 的补数，简称 减补数）是 $b^n-1-a$．在二进制下，数基补数叫做 $2$ 的补数（two's complement），又叫做 补码；缩减数基补数叫做 $1$ 的补数（ones' complement），又叫做 反码；在十进制下，数基补数又叫做 $10$ 的补数（ten's complement），缩减数基补数又叫做 $9$ 的补数（nine's complement）；其他进制以此类推．

对 $b$ 进制下的 $n$ 位数 $x,y$，当计算 $x-y$ 时，我们有如下方法（若结果超过 $n$ 位，则舍弃高位）：

1. 考虑 $x$ 的减补数 $x^{\prime }=b^n-1-x$，计算 $x^{\prime }+y=b^n-1-x+y$，则该结果的减补数即为答案．
2. 考虑 $y$ 的减补数 $y^{\prime }=b^n-1-y$，计算 $x+y^{\prime }=b^n-1+x-y$，直接加一即为答案．
3. 考虑 $x$ 的数基补数 $x^{\prime }=b^n-x$，计算 $x^{\prime }+y=b^n-x+y$，则该结果的数基补数即为答案．
4. 考虑 $y$ 的数基补数 $y^{\prime }=b^n-y$，计算 $x+y^{\prime }=b^n+x-y$，此即为答案．

另外，对 $k$ 进制下的数，我们设 $d=k-1$，则 $\cdots dd=:\bar{d}=\sum _{i=0}^{\mathrm{\infty }}d{k}^i=-1$，所以对 $n$ 位数 $x$，设其数基补数在 $k$ 进制下的表示为 $a_{n-1}\cdots a_1{a}_0$，则 $\bar{d}{a}_{n-1}\cdots a_1{a}_0$ 即为 $\sum _{i=0}^{n-1}{a}_i{k}^i+\sum _{i=n}^{\mathrm{\infty }}d{k}^i=k^n-x+(-k^n)=-x$．这种「无限位的数」的思想可以推广为 $p$ 进数（$p$-adic number）．

此外，我们有一个关于补数和无限循环小数的有趣定理：

证明

对定理中的 $a,b,p,l,n,k$，不难发现 ， 且 $(a,p)=(b,p)=1$．

对整数 ，令 $f(i)=b^i\cdot a/p-\lfloor b^i\cdot a/p\rfloor$，我们有

注意到 $pf(i)\in {\mathbf{N}}_{+}$ 且 $pf(i)\equiv a{b}^i(\mathrm{mod}p)$，因此 ．

令 $S_n=\sum _{i=0}^{n-1}f(ik)=\sum _{i=0}^{n-1}0.\overline{a_{ik+1}{a}_{ik+2}\cdots a_{nk}{a}_1{a}_2\cdots a_{ik}}$，我们可以在各个小数间「交换」若干位（例如 $0.\overline{142857}+0.\overline{285714}+0.\overline{571428}=0.\overline{141414}+0.\overline{282828}+0.\overline{575757}=0.\overline{14}+0.\overline{28}+0.\overline{57}=14/99+28/99+57/99=1$），则

进而

因此

若 $p\mid (b^k-1)$，注意到

$$(b^k-1)a/p=a_1{a}_2\cdots a_k.\overline{a_{k+1}{a}_{k+2}\cdots a_{nk}{a}_1{a}_2\cdots a_k}-0.\overline{a_1{a}_2\cdots a_{nk}},$$

则有 $a_{k+1}{a}_{k+2}\cdots a_{nk}{a}_1{a}_2\cdots a_k=a_1{a}_2\cdots a_{nk}$，进而 $a_1{a}_2\cdots a_k=a_{k+1}{a}_{k+2}\cdots a_{2k}=\cdots =a_{(n-1)k+1}{a}_{(n-1)k+2}\cdots a_{nk}$，即 $0.\overline{a_1{a}_2\cdots a_l}=0.\overline{a_1{a}_2\cdots a_k}$，这与 $l$ 的定义矛盾，因此 $p\nmid (b^k-1)$．

故存在正整数 ，使得

$$\sum _{i=0}^{n-1}{a}_{ik+1}{a}_{ik+2}\cdots a_{(i+1)k}=c(b^k-1).$$

推论

对上述的 $b,n,k,p$，有

$$\sum _{i=0}^{n-1}{b}^{ik}\equiv 0(\mathrm{mod}p).$$

广义进制系统

标准的进制系统中，基数 $b$ 总是一个固定的正数，每个数位在 $b$ 种不同的符号中选取，用以表示一个非负数（不考虑小数点和负号）．实际上仍有许多记数系统和进制系统有类似的特征，但不完全符合进制系统的规定，我们把这样的记数系统称为 广义进制系统 或 非标准进制系统（Non-standard positional numeral systems）．下面介绍几种常见的广义进制系统．

双射记数系统

标准的进制系统并不能和其表示的数字建立双射，如 $1$、$01$、$001$ 表示的数是相同的²，而 双射记数系统（bijective numeral system）可以和其表示的数字建立双射．

双射 $k$ 进制（$k\ge 1$）使用数集 $\{1,2,\dots ,k\}$ 来唯一表示一个数，规则如下：

1. 用空串表示 $0$；
2. 用非空串 $a_n\cdots a_1{a}_0$ 表示数 $a_n{k}^n+\cdots +a_1{k}^1+a_0{k}^0=\sum _{i=0}^n{a}_i{k}^i$．

对一个正数 $m$，设其双射 $k$ 进制下的表示为 $a_n\cdots a_1{a}_0$，则有：

其中 $f(x)=\lceil x\rceil -1$．

例如 Microsoft Excel 的列标签采用的就是双射 $26$ 进制．

在双射记数系统下，我们有 一进制，一进制下的非空串只由 $1$ 构成，串的长度即为其表示的数．

类似 补数法 下的叙述，在 的双射 $k$ 进制下，我们设 $d=k-1$，则 $\cdots dd=:\bar{d}=\sum _{i=0}^{\mathrm{\infty }}d{k}^i=-1$，进而 $\bar{d}k=0$，所以设 $x$ 在双射 $k$ 进制下的表示为 $a_{n-1}\cdots a_1{a}_0$，则 $\bar{d}k{a}_{n-1}\cdots a_1{a}_0$ 即为 $-x$．

下面是双射 $k$ 进制数的一些性质：

• 长度为 $l\ge 0$ 的数共有 $k^l$ 种．
• $k\ge 2$ 时，数 $n$ 在双射 $k$ 进制下表示的长度为 $\lfloor {\log }_k(n+1)(k-1)\rfloor$．
• $k\ge 2$ 时，若一个数 $n$ 在 $k$ 进制下的表示中不含 $0$，则其在 $k$ 进制下的表示和在双射 $k$ 进制下的表示相同．

双射 $k$ 进制转十进制和 $k$ 进制转十进制的代码相同，下面是十进制转双射 $k$ 进制的参考实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <algorithm>
#include <string>

// only non-negative
// 1 <= base && base < 36
std::string from_dec_bi(int x, int base) {
  std::string res;
  while (x > 0) {
    int q = (x + base - 1) / base - 1, r = x - q * base;
    x = q;

    // 写法 1
    res.push_back(r < 10 ? '0' + r : 'A' + r - 10);
    // 写法 2
    // const static std::string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // res.push_back(digits[r]);
  }
  std::reverse(res.begin(), res.end());
  return res;
}

有符号位数进制

有的进位制系统允许数位中出现负数，例如 平衡三进制．

Gray 码

主条目：格雷码

Gray 码又叫 循环二进制码 或 反射二进制码（reflected binary code，RBC），是一种特殊的二进制数字系统，常用于数据校验中．

非正基数进制

我们知道对于 $k$ 进制数 $a_n\cdots a_1{a}_0$，其表示的值为 $\sum _{i=0}^n{a}_i{k}^i$，我们稍加修改即可定义 $-k$ 进制数 ${a_n\cdots a_1{a}_0}_{(-k)}$ 表示 $\sum _{i=0}^n{a}_i(-k{)}^i$，其中 $a_n,\dots ,a_1,a_0\in \{0,1,\dots ,k-1\}$．例如 ${12345}_{(-10)}={8265}_{(10)}$．这种进制系统叫做 负底数进制（negative-base system）．

类似地，我们也可以定义 复底数进制（complex-base system），如 $2\mathrm{i}$ 进制（quater-imaginary base、quater-imaginary numeral system），我们还可以定义 非整数进位制（non-integer base of numeration）用于表示实数的 $\beta$ 展开（$\beta$-expansion）等．

混合基数进制

标准的进制系统中，每一个数位对应的基数都是固定的，而混合基数进制允许每一个数位对应不同的基数．混合基数进制系统最常见的应用就是计时：小时采用 $24$ 进制，分钟和秒采用 $60$ 进制．

$a_n\cdots a_1{a}_0$ 在 $b$ 进制下表示的数为 $\sum _{i=0}^n{a}_i{b}^i$，而在混合基数进制下，其表示的数为 $\sum _{i=0}^n{a}_i\prod _{j=0}^{i-1}{b}_j$，其中 $b_j$ 为 $a_j$ 对应的基数．

在算法竞赛中，最常见的混合基数进制系统是 阶乘进制（factorial number system），其中的数可以记作 ${a_n\cdots a_1{a}_0}_{!}$，其表示的数为 $\sum _{i=0}^n{a}_{i}i!$³．阶乘进制在算法竞赛中的应用可参见 Lehmer 码/Cantor 展开．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <algorithm>
#include <string>

// only non-negative
std::string from_dec_factorial(int x) {
  if (x == 0) return "0";
  std::string res;
  int base = 1;
  while (x) {
    int r = x % base;
    x /= base++;

    // 写法 1
    res.push_back(r < 10 ? '0' + r : 'A' + r - 10);
    // 写法 2
    // const static std::string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    // res.push_back(digits[r]);
  }
  std::reverse(res.begin(), res.end());
  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <cctype>
#include <string>

// only non-negative
int to_dec_factorial(std::string const& s) {
  int res = 0, base = s.size();
  for (char c : s) {
    res *= base--;
    if (isdigit(c))
      res += c - '0';
    else if (isupper(c))
      res += c - 'A' + 10;
    else if (islower(c))
      res += c - 'a' + 10;
  }
  return res;
}

C++ 中的实现

对于非负数，C++ 中用 <前缀><数位><后缀> 表示一个整数字面量，其中 <数位> 和 <后缀> 均可以为空．<后缀> 用于表示字面量的类型，如 u 或 U 表示该字面量为 unsigned、l 或 L 表示该字面量为 long 等．对于 <前缀>：

• 当 <前缀> 为 0x 或 0X 时表示十六进制字面量，此时 <数位> 中的字符只能在 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, A, b, B, c, C, d, D, e, E, f, F 中选取．例如 0x1234ABCD 为 ${\text{1234ABCD}}_{(16)}=305441741$；
• 当 <前缀> 为 0 时表示八进制字面量，此时 <数位> 中的字符只能在 0, 1, 2, 3, 4, 5, 6, 7 中选取．例如 01234567 为 ${1234567}_{(8)}=342391$；⁵
• 当 <前缀> 为 1、2、3、4、5、6、7、8 或 9 时表示十进制字面量，此时 <数位> 中的字符只能在 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 中选取；
• C++14 起，当 <前缀> 为 0b 或 0B 时表示二进制字面量，此时 <数位> 中的字符只能在 0, 1 中选取．例如 0b11001010 为 ${11001010}_{(2)}=202$．

参考资料与注释

• Positional notation - Wikipedia
• Method of complements - Wikipedia
• Non-standard positional numeral systems - Wikipedia
• Bijective numeration - Wikipedia
• Midy's theorem - Wikipedia
• N3472 - Binary Literals in the C++ Core Language

本页面最近更新：2026/1/30 14:50:40，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, c-forrest, Enter-tainer, hhc0001, Ir1d, KingMario, ksyx, Lutra-Fs, MegaOwIer, niujiaxing, StudyingFather, TOMWT-qwq, ZnPdCo
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用