跳转至

# 进位制

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

一般地，我们常将一个 𝑛 n 进制的数记作 (𝑎 𝑘⋯𝑎 1 𝑎 0)𝑛(a k⋯a 1 a 0)n、(𝑎 𝑘⋯𝑎 1 𝑎 0)(𝑛)(a k⋯a 1 a 0)(n)、𝑎 𝑘⋯𝑎 1 𝑎 0(𝑛)a k⋯a 1 a 0(n)、𝑎 𝑘⋯𝑎 1 𝑎 0 𝑛 a k⋯a 1 a 0 n 等．若基数隐含在上下文中我们也可以省略下标．注意此处的 𝑎 𝑘⋯𝑎 1 𝑎 0 a k⋯a 1 a 0 并不是 𝑘 +1 k+1 个数的乘积，而是一串序列．

对于 𝑘 k 进制数 𝑎 𝑛⋯𝑎 1 𝑎 0 a n⋯a 1 a 0，其表示的值为 𝑎 𝑛 𝑘 𝑛 +⋯ +𝑎 1 𝑘 1 +𝑎 0 𝑘 0 =∑𝑛 𝑖=0 𝑎 𝑖 𝑘 𝑖 a n k n+⋯+a 1 k 1+a 0 k 0=∑i=0 n a i k i；对一个数 𝑚 m，设其 𝑘 k 进制下的表示为 𝑎 𝑛⋯𝑎 1 𝑎 0 a n⋯a 1 a 0，则有：

𝑎 0=𝑚−𝑞 0 𝑘,𝑞 0=𝑓(𝑚/𝑘),𝑎 1=𝑞 0−𝑞 1 𝑘,𝑞 1=𝑓(𝑞 0/𝑘),⋮⋮𝑎 𝑛=𝑞 𝑛−1−𝑞 𝑛 𝑘,𝑞 𝑛=𝑓(𝑞 𝑛−1/𝑘)=0,a 0=m−q 0 k,q 0=f(m/k),a 1=q 0−q 1 k,q 1=f(q 0/k),⋮⋮a n=q n−1−q n k,q n=f(q n−1/k)=0,

其中 𝑓(𝑥) =⌊𝑥⌋f(x)=⌊x⌋．

数 𝑛 n 在 𝑘 k 进制下表示的长度为 ⌈l o g 𝑘⁡(𝑛 +1)⌉⌈log k⁡(n+1)⌉．

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

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

## 不同进位制间的转换

### 十进制转其他进制

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

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

例子

将 3 5.2 5 35.25 转化为二进制数．

整数部分：

3 5/2=1 7…1,1 7/2=8…1,8/2=4…0,4/2=2…0,2/2=1…0,1/2=0…1.35/2=17…1,17/2=8…1,8/2=4…0,4/2=2…0,2/2=1…0,1/2=0…1.

小数部分：

0.2 5×2=0.5…0,0.5×2=1…1.0.25×2=0.5…0,0.5×2=1…1.

即 3 5.2 5 =(1 0 0 0 1 1.0 1)2 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 𝑖 2 i 次即可，其中 𝑖 i 为当前位的位数，个位的位数为 0 0．

例子

将 (1 1 0 1 0.0 1)2(11010.01)2 转换为十进制数．

(1 1 0 1 0.0 1)2=+ 1×2 4+1×2 3+0×2 2+1×2 1+0×2 0=+ 0×2−1+1×2−2=2 6.2 5.(11010.01)2=+ 1×2 4+1×2 3+0×2 2+1×2 1+0×2 0=+ 0×2−1+1×2−2=26.25.

即 (1 1 0 1 0.0 1)2 =(2 6.2 5)1 0(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 2 3=8），一个十六进制位可以用 4 个二进制位来表示（2 4 =1 6 2 4=16），反之同理．

## 补数法

另请参阅：反码与补码

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

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

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

1. 考虑 𝑥 x 的减补数 𝑥′ =𝑏 𝑛 −1 −𝑥 x′=b n−1−x，计算 𝑥′ +𝑦 =𝑏 𝑛 −1 −𝑥 +𝑦 x′+y=b n−1−x+y，则该结果的减补数即为答案．
2. 考虑 𝑦 y 的减补数 𝑦′ =𝑏 𝑛 −1 −𝑦 y′=b n−1−y，计算 𝑥 +𝑦′ =𝑏 𝑛 −1 +𝑥 −𝑦 x+y′=b n−1+x−y，直接加一即为答案．
3. 考虑 𝑥 x 的数基补数 𝑥′ =𝑏 𝑛 −𝑥 x′=b n−x，计算 𝑥′ +𝑦 =𝑏 𝑛 −𝑥 +𝑦 x′+y=b n−x+y，则该结果的数基补数即为答案．
4. 考虑 𝑦 y 的数基补数 𝑦′ =𝑏 𝑛 −𝑦 y′=b n−y，计算 𝑥 +𝑦′ =𝑏 𝑛 +𝑥 −𝑦 x+y′=b n+x−y，此即为答案．

另外，对 𝑘 k 进制下的数，我们设 𝑑 =𝑘 −1 d=k−1，则 ⋯𝑑 𝑑 =:――𝑑 =∑∞𝑖=0 𝑑 𝑘 𝑖 = −1⋯d d=:d―=∑i=0∞d k i=−1，所以对 𝑛 n 位数 𝑥 x，设其数基补数在 𝑘 k 进制下的表示为 𝑎 𝑛−1⋯𝑎 1 𝑎 0 a n−1⋯a 1 a 0，则 ――𝑑 𝑎 𝑛−1⋯𝑎 1 𝑎 0 d―a n−1⋯a 1 a 0 即为 ∑𝑛−1 𝑖=0 𝑎 𝑖 𝑘 𝑖 +∑∞𝑖=𝑛 𝑑 𝑘 𝑖 =𝑘 𝑛 −𝑥 +( −𝑘 𝑛) = −𝑥∑i=0 n−1 a i k i+∑i=n∞d k i=k n−x+(−k n)=−x．这种「无限位的数」的思想可以推广为 𝑝 p 进数（𝑝 p-adic number）．

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

Midy 定理

设 𝑎 a 是正整数，𝑝 p 是正素数，𝑎/𝑝 a/p 在 𝑏 b 进制下的表示为 0.―――――𝑎 1 𝑎 2⋯𝑎 𝑙 0.a 1 a 2⋯a l―，其中 𝑙 l 为（最短）循环节长度．若 𝑙 l 是偶数4，设 𝑙 =2 𝑘 l=2 k，则 𝑎 1 𝑎 2⋯𝑎 𝑘 a 1 a 2⋯a k 是 𝑎 𝑘+1 𝑎 𝑘+2⋯𝑎 2 𝑘 a k+1 a k+2⋯a 2 k 的减补数，即：

- 𝑎 𝑖 +𝑎 𝑖+𝑘 =𝑏 a i+a i+k=b，
- 𝑎 1 𝑎 2⋯𝑎 𝑘 +𝑎 𝑘+1 𝑎 𝑘+2⋯𝑎 2 𝑘 =𝑏 𝑘 −1 a 1 a 2⋯a k+a k+1 a k+2⋯a 2 k=b k−1．

进一步，若 𝑙 l 有非平凡因子 𝑘 k，设 𝑙 =𝑛 𝑘 l=n k，则 ∑𝑛−1 𝑖=0 𝑎 𝑖 𝑘+1 𝑎 𝑖 𝑘+2⋯𝑎(𝑖+1)𝑘∑i=0 n−1 a i k+1 a i k+2⋯a(i+1)k 是 𝑏 𝑘 −1 b k−1 的倍数．

例子

对于 1/1 9 =0.――――――――――――0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1 =0.―――――0 3 2 7 4 5(8)1/19=0.052 631 578 947 368 421―=0.032 745―(8)，我们有：

- 0 5 2 6 3 1 5 7 8 +9 4 7 3 6 8 4 2 1 =9 9 9 9 9 9 9 9 9 052 631 578+947 368 421=999 999 999，
- 0 5 2 +6 3 1 +5 7 8 +9 4 7 +3 6 8 +4 2 1 =3 ×9 9 9 052+631+578+947+368+421=3×999，
- 0 3 2(8) +7 4 5(8) =7 7 7(8)032(8)+745(8)=777(8)，
- 0 3(8) +2 7(8) +4 5(8) =7 7(8)03(8)+27(8)+45(8)=77(8)．

证明

对定理中的 𝑎,𝑏,𝑝,𝑙,𝑛,𝑘 a,b,p,l,n,k，不难发现 1 ≤𝑎 <𝑝 1≤a<p，𝑏 >1 b>1 且 (𝑎,𝑝) =(𝑏,𝑝) =1(a,p)=(b,p)=1．

对整数 0 ≤𝑖 <𝑙 0≤i<l，令 𝑓(𝑖) =𝑏 𝑖 ⋅𝑎/𝑝 −⌊𝑏 𝑖 ⋅𝑎/𝑝⌋f(i)=b i⋅a/p−⌊b i⋅a/p⌋，我们有

0<𝑓(𝑖)=0.―――――――――――𝑎 𝑖+1 𝑎 𝑖+2⋯𝑎 𝑛 𝑘 𝑎 1 𝑎 2⋯𝑎 𝑖<1⟹0<𝑝 𝑓(𝑖)<𝑝.0<f(i)=0.a i+1 a i+2⋯a n k a 1 a 2⋯a i―<1⟹0<p f(i)<p.

注意到 𝑝 𝑓(𝑖) ∈𝐍+p f(i)∈N+ 且 𝑝 𝑓(𝑖) ≡𝑎 𝑏 𝑖(m o d 𝑝)p f(i)≡a b i(mod p)，因此 𝑝 𝑓(𝑖) =𝑎 𝑏 𝑖 m o d 𝑝 p f(i)=a b i mod p．

令 𝑆 𝑛 =∑𝑛−1 𝑖=0 𝑓(𝑖 𝑘) =∑𝑛−1 𝑖=0 0.――――――――――――𝑎 𝑖 𝑘+1 𝑎 𝑖 𝑘+2⋯𝑎 𝑛 𝑘 𝑎 1 𝑎 2⋯𝑎 𝑖 𝑘 S n=∑i=0 n−1 f(i k)=∑i=0 n−1 0.a i k+1 a i k+2⋯a n k a 1 a 2⋯a i k―，我们可以在各个小数间「交换」若干位（例如 0.――――1 4 2 8 5 7 +0.――――2 8 5 7 1 4 +0.――――5 7 1 4 2 8 =0.――――1 4 1 4 1 4 +0.――――2 8 2 8 2 8 +0.――――5 7 5 7 5 7 =0.――1 4 +0.――2 8 +0.――5 7 =1 4/9 9 +2 8/9 9 +5 7/9 9 =1 0.14 28 57―+0.28 57 14―+0.57 14 28―=0.141414―+0.282828―+0.575757―=0.14―+0.28―+0.57―=14/99+28/99+57/99=1），则

𝑆 𝑛=𝑛−1∑𝑖=0 0.―――――――――𝑎 𝑖 𝑘+1 𝑎 𝑖 𝑘+2⋯𝑎(𝑖+1)𝑘=𝑛−1∑𝑖=0 𝑎 𝑖 𝑘+1 𝑎 𝑖 𝑘+2⋯𝑎(𝑖+1)𝑘/(𝑏 𝑘−1),S n=∑i=0 n−1 0.a i k+1 a i k+2⋯a(i+1)k―=∑i=0 n−1 a i k+1 a i k+2⋯a(i+1)k/(b k−1),

进而

𝑝 𝑆 𝑛=𝑝 𝑛−1∑𝑖=0 𝑎 𝑖 𝑘+1 𝑎 𝑖 𝑘+2⋯𝑎(𝑖+1)𝑘/(𝑏 𝑘−1)=𝑛−1∑𝑖=0(𝑎 𝑏 𝑖 𝑘 m o d 𝑝),p S n=p∑i=0 n−1 a i k+1 a i k+2⋯a(i+1)k/(b k−1)=∑i=0 n−1(a b i k mod p),

因此

𝑛−1∑𝑖=0 𝑎 𝑖 𝑘+1 𝑎 𝑖 𝑘+2⋯𝑎(𝑖+1)𝑘=(𝑏 𝑘−1)∑𝑛−1 𝑖=0(𝑎 𝑏 𝑖 𝑘 m o d 𝑝)𝑝.∑i=0 n−1 a i k+1 a i k+2⋯a(i+1)k=(b k−1)∑i=0 n−1(a b i k mod p)p.

若 𝑝 ∣(𝑏 𝑘−1)p∣(b k−1)，注意到

(𝑏 𝑘−1)𝑎/𝑝=𝑎 1 𝑎 2⋯𝑎 𝑘.―――――――――――𝑎 𝑘+1 𝑎 𝑘+2⋯𝑎 𝑛 𝑘 𝑎 1 𝑎 2⋯𝑎 𝑘−0.――――――𝑎 1 𝑎 2⋯𝑎 𝑛 𝑘,(b k−1)a/p=a 1 a 2⋯a k.a k+1 a k+2⋯a n k a 1 a 2⋯a k―−0.a 1 a 2⋯a n k―,

则有 𝑎 𝑘+1 𝑎 𝑘+2⋯𝑎 𝑛 𝑘 𝑎 1 𝑎 2⋯𝑎 𝑘 =𝑎 1 𝑎 2⋯𝑎 𝑛 𝑘 a k+1 a k+2⋯a n k a 1 a 2⋯a k=a 1 a 2⋯a n k，进而 𝑎 1 𝑎 2⋯𝑎 𝑘 =𝑎 𝑘+1 𝑎 𝑘+2⋯𝑎 2 𝑘 =⋯ =𝑎(𝑛−1)𝑘+1 𝑎(𝑛−1)𝑘+2⋯𝑎 𝑛 𝑘 a 1 a 2⋯a k=a k+1 a k+2⋯a 2 k=⋯=a(n−1)k+1 a(n−1)k+2⋯a n k，即 0.―――――𝑎 1 𝑎 2⋯𝑎 𝑙 =0.―――――𝑎 1 𝑎 2⋯𝑎 𝑘 0.a 1 a 2⋯a l―=0.a 1 a 2⋯a k―，这与 𝑙 l 的定义矛盾，因此 𝑝 ∤(𝑏 𝑘−1)p∤(b k−1)．

故存在正整数 𝑐 =∑𝑛−1 𝑖=0(𝑎 𝑏 𝑖 𝑘 m o d 𝑝)𝑝 c=∑i=0 n−1(a b i k mod p)p，使得

𝑛−1∑𝑖=0 𝑎 𝑖 𝑘+1 𝑎 𝑖 𝑘+2⋯𝑎(𝑖+1)𝑘=𝑐(𝑏 𝑘−1).∑i=0 n−1 a i k+1 a i k+2⋯a(i+1)k=c(b k−1).
推论

对上述的 𝑏,𝑛,𝑘,𝑝 b,n,k,p，有

𝑛−1∑𝑖=0 𝑏 𝑖 𝑘≡0(m o d 𝑝).∑i=0 n−1 b i k≡0(mod p).

## 广义进制系统

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

### 双射记数系统

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

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

1. 用空串表示 0 0；
2. 用非空串 𝑎 𝑛⋯𝑎 1 𝑎 0 a n⋯a 1 a 0 表示数 𝑎 𝑛 𝑘 𝑛 +⋯ +𝑎 1 𝑘 1 +𝑎 0 𝑘 0 =∑𝑛 𝑖=0 𝑎 𝑖 𝑘 𝑖 a n k n+⋯+a 1 k 1+a 0 k 0=∑i=0 n a i k i．

对一个正数 𝑚 m，设其双射 𝑘 k 进制下的表示为 𝑎 𝑛⋯𝑎 1 𝑎 0 a n⋯a 1 a 0，则有：

𝑎 0=𝑚−𝑞 0 𝑘,𝑞 0=𝑓(𝑚/𝑘),𝑎 1=𝑞 0−𝑞 1 𝑘,𝑞 1=𝑓(𝑞 0/𝑘),⋮⋮𝑎 𝑛=𝑞 𝑛−1−𝑞 𝑛 𝑘,𝑞 𝑛=𝑓(𝑞 𝑛−1/𝑘)=0,a 0=m−q 0 k,q 0=f(m/k),a 1=q 0−q 1 k,q 1=f(q 0/k),⋮⋮a n=q n−1−q n k,q n=f(q n−1/k)=0,

其中 𝑓(𝑥) =⌈𝑥⌉ −1 f(x)=⌈x⌉−1．

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

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

类似 补数法 下的叙述，在 𝑘 >1 k>1 的双射 𝑘 k 进制下，我们设 𝑑 =𝑘 −1 d=k−1，则 ⋯𝑑 𝑑 =:――𝑑 =∑∞𝑖=0 𝑑 𝑘 𝑖 = −1⋯d d=:d―=∑i=0∞d k i=−1，进而 ――𝑑 𝑘 =0 d―k=0，所以设 𝑥 x 在双射 𝑘 k 进制下的表示为 𝑎 𝑛−1⋯𝑎 1 𝑎 0 a n−1⋯a 1 a 0，则 ――𝑑 𝑘 𝑎 𝑛−1⋯𝑎 1 𝑎 0 d―k a n−1⋯a 1 a 0 即为 −𝑥−x．

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

- 长度为 𝑙 ≥0 l≥0 的数共有 𝑘 𝑙 k l 种．
- 𝑘 ≥2 k≥2 时，数 𝑛 n 在双射 𝑘 k 进制下表示的长度为 ⌊l o g 𝑘⁡(𝑛 +1)(𝑘 −1)⌋⌊log k⁡(n+1)(k−1)⌋．
- 𝑘 ≥2 k≥2 时，若一个数 𝑛 n 在 𝑘 k 进制下的表示中不含 0 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 进制数 𝑎 𝑛⋯𝑎 1 𝑎 0 a n⋯a 1 a 0，其表示的值为 ∑𝑛 𝑖=0 𝑎 𝑖 𝑘 𝑖∑i=0 n a i k i，我们稍加修改即可定义 −𝑘−k 进制数 𝑎 𝑛⋯𝑎 1 𝑎 0(−𝑘)a n⋯a 1 a 0(−k) 表示 ∑𝑛 𝑖=0 𝑎 𝑖( −𝑘)𝑖∑i=0 n a i(−k)i，其中 𝑎 𝑛,…,𝑎 1,𝑎 0 ∈{0,1,…,𝑘 −1}a n,…,a 1,a 0∈{0,1,…,k−1}．例如 1 2 3 4 5(−1 0) =8 2 6 5(1 0)12345(−10)=8265(10)．这种进制系统叫做 负底数进制（negative-base system）．

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

### 混合基数进制

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

𝑎 𝑛⋯𝑎 1 𝑎 0 a n⋯a 1 a 0 在 𝑏 b 进制下表示的数为 ∑𝑛 𝑖=0 𝑎 𝑖 𝑏 𝑖∑i=0 n a i b i，而在混合基数进制下，其表示的数为 ∑𝑛 𝑖=0 𝑎 𝑖∏𝑖−1 𝑗=0 𝑏 𝑗∑i=0 n a i∏j=0 i−1 b j，其中 𝑏 𝑗 b j 为 𝑎 𝑗 a j 对应的基数．

在算法竞赛中，最常见的混合基数进制系统是 阶乘进制（factorial number system），其中的数可以记作 𝑎 𝑛⋯𝑎 1 𝑎 0 !a n⋯a 1 a 0 !，其表示的数为 ∑𝑛 𝑖=0 𝑎 𝑖 𝑖!∑i=0 n a i i!3．阶乘进制在算法竞赛中的应用可参见 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` 为 1 2 3 4 A B C D(1 6) =3 0 5 4 4 1 7 4 1 1234ABCD(16)=305 441 741；
- 当 `<前缀>` 为 `0` 时表示八进制字面量，此时 `<数位>` 中的字符只能在 `0, 1, 2, 3, 4, 5, 6, 7` 中选取．例如 `01234567` 为 1 2 3 4 5 6 7(8) =3 4 2 3 9 1 1234567(8)=342391；5
- 当 `<前缀>` 为 `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` 为 1 1 0 0 1 0 1 0(2) =2 0 2 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

1. 有的地区使用「,,」表示小数点． ↩

2. 我们把最高的非 0 0 位之前的 0 0 称为 前导零（leading zero）．类似地，我们可以定义 后导零（trailing zero）． ↩

3. 𝑎 𝑖 a i 对应的基数是 𝑖 +1 i+1，0 ≤𝑎 𝑖 ≤𝑖 0≤a i≤i．注意到 (𝑛 +1)! −𝑛! =𝑛 ⋅𝑛!(n+1)!−n!=n⋅n!，所以数在阶乘进制下的表示在去除前导零的情况下是唯一的． ↩

4. 当 𝑎 =1 a=1 时，在十进制下满足该条件的素数序列是 A028416． ↩

5. `0` 是八进制字面量． ↩

> 本页面最近更新：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 协议之条款下提供，附加条款亦可能应用