OI-wiki 数字系统记数系统导览从概念定义到进位制转换与广义进制实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读数字系统numeral system又称记数系统是算法竞赛中处理进制转换、位运算、负数编码、排列排名等问题的底层语言。本篇以 OI-wiki 的「数字系统」章节为骨架先厘清数学中的 number system 与记数系统 numeral system 的概念差异再系统展开 OI 中最常遇到的进位制转换、补数法反码/补码、双射记数系统、阶乘进制与平衡三进制等广义进制系统并给出可直接复用的 C 参考实现与源码级解读。读完本文你将掌握进制间的相互换算原理、补数法背后的减法电路思想以及在竞赛中正确使用各进制工具的能力。数字系统给「数」做编码的工具先厘清两个易混概念number system 与 numeral system在数学中number system数字系统指的是一类集合例如整数集 $\mathbf{Z}$、复数集 $\mathbf{C}$ 等——它描述的是数本身的代数结构。而 OI-wiki 此处的「数字系统」numeral system含义完全不同数字系统又称记数系统指的是用以表示数字的书写系统如印度–阿拉伯数字系统、罗马数字、苏州码子等。数字系统是我们给数做编码的工具。换言之numeral system 关心的是怎么把一个数写下来例如罗马数字 $\text{XLII}$、二进制数 $101010_{(2)}$ 和十进制数 $42$ 都能对应到同一个数。正是这种符号串 对应规则的编码视角让数字系统成为计算与算法竞赛的基石。数字系统的本质符号串与对应规则一个数字系统下的数字本质上是一串符号同时有一套规则将这串符号和对应的数一一对应起来。以最常见的例子数字系统符号串对应的数罗马数字$\text{XLII}$$42$二进制$101010_{(2)}$$42$十进制$42$$42$三套记数系统用完全不同的符号串编码了同一个数值——这正是数字系统是编码工具的含义同一个数可以有多种不同的写法而数字系统决定了如何从写法还原数值。从算法竞赛的角度看OI 选手通常只关心不同数字系统间的转化关系即 进位制 所讨论的内容。因此本文接下来的主体部分将围绕进位制及其各种变体展开。进位制有限符号表示所有自然数的记数系统进位制又称进位系统carry system、位置记法positional notation、位值记数法place-value notation是一种能用有限种符号表示所有自然数的数字系统。这一节完整继承了 docs/math/numeral-sys/base.md 的核心内容并在关键处补充仓库源码作为实现依据。基数、进位与数的展开式一种进位制可以使用的符号数目称为基数radix或底数base。基数为 $n$ 的进位制称为 $n$ 进制$n1$。例如十进制通常只使用0,1,2,3,4,5,6,7,8,9这十个符号。进位指的是「当一个数字的某一位达到基数时将其置为 0 并使高一位的数加一」的操作。这是位置记法能用有限符号表示任意大的数的根本机制。记法上一个 $n$ 进制的数通常记作 $(a_k\cdots a_1a_0)n$也可写作 $(a_k\cdots a_1a_0){(n)}$ 或省略下标。注意这里的 $a_k\cdots a_1a_0$ 不是乘积而是一串序列。值的展开公式对 $k$ 进制数 $a_n\cdots a_1a_0$其表示的值为$$ a_nk^n\cdotsa_1k^1a_0k^0\sum_{i0}^n a_ik^i $$逆运算十进制 → k 进制对一个数 $m$设其 $k$ 进制表示为 $a_n\cdots a_1a_0$则有$$ \begin{array}{cc} a_0m-q_0k,q_0f(m/k),\ a_1q_0-q_1k,q_1f(q_0/k),\ \vdots\vdots\ a_nq_{n-1}-q_nk,q_nf(q_{n-1}/k)0, \end{array} $$其中 $f(x)\lfloor x\rfloor$。这套反复除基数取余数的算法正是所有十进制转其他进制程序的理论原型。位数公式数 $n$ 在 $k$ 进制下表示的长度为 $\lceil\log_k (n1)\rceil$。这一结论可用于快速估算数据范围与字符串长度。此外通过添加小数点「$.$」表示小数、负号「$-$」表示负数、上划线表示无限循环小数为方便阅读可每隔若干数位添加间隔符号如空格、,、如 $12~345$ 表示 $12345$。计算机中常用的进位制为二进制、八进制和十六进制。不同进位制间的转换十进制转其他进制以二进制为例。整数部分不断执行除 $2$ 操作直至商数为 $0$之后从下到上取所有余数小数部分则不断乘 $2$取整数部分结果再用剩余小数部分重复直至小数部分全为 $0$之后从上到下取整数部分。??? example 例子 将 $35.25$ 转化为二进制数整数部分 $$ \begin{aligned} 35/217 \dots 1,\\ 17/28 \dots 1,\\ 8/24 \dots 0,\\ 4/22 \dots 0,\\ 2/21 \dots 0,\\ 1/20 \dots 1. \end{aligned} $$ 小数部分 $$ \begin{aligned} 0.25\times 20.5 \dots 0,\\ 0.5\times 21 \dots 1. \end{aligned} $$ 即 $35.25 (100011.01)_2$仓库中的参考实现在 docs/math/code/base/base_1.cpp 的from_dec段对应--8-- [start:from_dec]。从源码可以看到它额外处理了两个工程细节// 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 base 36超过 10 的数位用A~Z表示对应A r - 10特判x 0返回0避免空串由于余数是从低位到高位产生的最后需要std::reverse一次。其他进制转十进制二进制转十进制只需将每个位的值乘以 $2^i$$i$ 为当前位位数个位位数为 $0$后求和。??? example 例子 将 $(11010.01)_{2}$ 转换为十进制数$$ \begin{aligned} (11010.01)_{2}\phantom{~}1\times 2^41\times 2^30\times 2^21\times 2^10\times 2^0\\ \phantom{}~0\times 2^{-1}1\times 2^{-2} \\ 26.25. \end{aligned} $$仓库中to_dec段对应--8-- [start:to_dec]的实现是典型的乘基数累加// 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; }注意它对大写、小写字母均做了兼容这与from_dec只输出大写形成闭环——to_dec可以解析from_dec产生的任意字符串。二进制/八进制/十六进制间的相互转换由于 $2^38$、$2^416$一个八进制位可以用 3 个二进制位表示一个十六进制位可以用 4 个二进制位表示反之同理。因此在 2/8/16 进制之间互转时无需经过十进制中转直接按位分组/展开即可这也是竞赛中手算与位运算优化的常用技巧。补数法用正数表示负数让减法退化为加法补数法method of complements是用正数表示负数的方法使得可以用与正数加法相同的算法/电路/机械结构来计算减法。它被广泛用于计算器与计算机的设计中用以简化结构。详细衔接可参阅 docs/math/bit.md 的「整数与位序列」一节。数基补数与缩减数基补数对 $b$ 进制下 $n$ 位数 $a$数基补数radix complement称为 $b$ 的补数是 $b^n-a$缩减数基补数diminished radix complement称为 $b-1$ 的补数简称减补数是 $b^n-1-a$。在二进制下数基补数叫2 的补数twos complement即常说的补码缩减数基补数叫1 的补数ones complement即反码。在十进制下对应10 的补数与9 的补数其他进制以此类推。四种补数减法对 $b$ 进制下的 $n$ 位数 $x,y$计算 $x-y$ 时若结果超过 $n$ 位则舍弃高位有四种等价方法考虑 $x$ 的减补数 $xb^n-1-x$计算 $xyb^n-1-xy$则该结果的减补数即为答案考虑 $y$ 的减补数 $yb^n-1-y$计算 $xyb^n-1x-y$直接加一即为答案考虑 $x$ 的数基补数 $xb^n-x$计算 $xyb^n-xy$则该结果的数基补数即为答案考虑 $y$ 的数基补数 $yb^n-y$计算 $xyb^nx-y$此即为答案。方法 2 与方法 4 的差异一个加一一个不加体现了数基补数与减补数之间相差 1 的本质关系。现代计算机的整数减法器正是基于方法 4取减数的补码再相加实现的。从无限位的数到 $p$ 进数对 $k$ 进制下的数设 $dk-1$则 $\cdots dd:\overline{d}\sum_{i0}^{\infty} dk^i-1$。于是对 $n$ 位数 $x$设其数基补数在 $k$ 进制下表示为 $a_{n-1}\cdots a_1a_0$则 $\overline{d}a_{n-1}\cdots a_1a_0$ 即为$$ \sum_{i0}^{n-1}a_ik^i\sum_{in}^{\infty} dk^ik^n-x(-k^n)-x $$这种无限位的数的思想可以推广为 $p$ 进数$p$-adic number——一个连接初等进制理论到现代数论的桥梁概念。Midy 定理补数与无限循环小数的美丽联系Midy 定理设 $a$ 是正整数$p$ 是正素数$a/p$ 在 $b$ 进制下的表示为 $0.\overline{a_1a_2\cdots a_l}$其中 $l$ 为最短循环节长度。若 $l$ 是偶数设 $l2k$则 $a_1a_2\cdots a_k$ 是 $a_{k1}a_{k2}\cdots a_{2k}$ 的减补数即$a_ia_{ik}b$$a_1a_2\cdots a_ka_{k1}a_{k2}\cdots a_{2k}b^k-1$。进一步若 $l$ 有非平凡因子 $k$设 $lnk$则 $\sum_{i0}^{n-1}a_{ik1}a_{ik2}\cdots a_{(i1)k}$ 是 $b^k-1$ 的倍数。??? example 例子 对于 $1/190.\overline{052~631~578~947~368~421}0.\overline{032~745}_{(8)}$有- $052~631~578947~368~421999~999~999$ - $0526315789473684213\times 999$ - $032_{(8)}745_{(8)}777_{(8)}$ - $03_{(8)}27_{(8)}45_{(8)}77_{(8)}$ 当 $a1$ 时十进制下满足该条件的素数序列即著名的 A028416 序列。Midy 定理的证明在 docs/math/numeral-sys/base.md 中给出核心是利用 $pf(i)ab^i\bmod p$ 的周期性在循环小数的各位之间交换数位进行求和由证明还可以推出推论$\sum_{i0}^{n-1} b^{ik}\equiv 0\pmod p$。广义进制系统跳出固定基数标准进制系统中基数 $b$ 总是固定的正数每个数位在 $b$ 种符号中选取。仍有许多记数系统有类似特征但不完全符合标准规定这类系统统称广义进制系统或非标准进制系统Non-standard positional numeral systems。OI-wiki 在本节依次介绍了四类常见变体。双射记数系统标准进制系统无法与数字建立双射——$1$、$01$、$001$ 表示同一个数高位的 0 即前导零。而双射记数系统bijective numeral system使用数集 ${1,2,\dots,k}$ 唯一表示一个数用空串表示 $0$用非空串 $a_n\cdots a_1a_0$ 表示数 $a_nk^n\cdotsa_1k^1a_0k^0$。对一个正数 $m$其双射 $k$ 进制表示同样通过反复除 $k$ 获得但这里的 $f(x)\lceil x\rceil-1$注意与标准进制的 $f(x)\lfloor x\rfloor$ 不同。一个非常贴近生活的例子Microsoft Excel 的列标签A、B、…、Z、AA、AB…采用的就是双射 26 进制。当 $k1$ 时即一进制unary numeral system非空串只由 $1$ 构成串的长度就是其表示的数。仓库参考实现位于 docs/math/code/base/base_1.cpp 的from_dec_bi段// 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; res.push_back(r 10 ? 0 r : A r - 10); } std::reverse(res.begin(), res.end()); return res; }关键在q (x base - 1) / base - 1用向上取整再减一实现 $f(x)\lceil x\rceil-1$。双射记数系统还有若干实用性质长度为 $l\geq 0$ 的数共有 $k^l$ 种$k\geq 2$ 时数 $n$ 在双射 $k$ 进制下表示的长度为 $\lfloor\log_k (n1)(k-1)\rfloor$$k\geq 2$ 时若 $n$ 在 $k$ 进制下的表示不含 $0$则其在标准 $k$ 进制和双射 $k$ 进制下的表示相同。顺带一提在 $k1$ 的双射 $k$ 进制下同样有 $\overline{d}-1$$dk-1$进而 $\overline{d}k0$因此 $x$ 的相反数可以表示为 $\overline{d}ka_{n-1}\cdots a_1a_0$——补数思想在广义进制下依然成立。有符号位数进制与 Gray 码有符号位数进制允许数位中出现负数最著名的例子是平衡三进制balanced ternary详见 docs/math/numeral-sys/balanced-ternary.md它用-1,0,1三个数字写作时用Z代替-1表示数负数只需把正数各位取反且每个十进制数对应唯一的平衡三进制表示。Gray 码又叫循环二进制码或反射二进制码reflected binary codeRBC是一种特殊的二进制数字系统相邻两个数只有一位不同常用于数据校验。其转换公式为 $G(n)n\oplus\lfloor n/2\rfloor$逆变换为反复异或详见 docs/math/numeral-sys/gray-code.md。Gray 码还可用 $k$ 位码序列构造 $k$ 维超立方体顶点的哈密尔顿回路并可用于求解汉诺塔问题。非正基数进制与更远的推广将标准进制的值公式 $\sum_{i0}^n a_ik^i$ 稍加修改即可定义负底数进制$-k$ 进制数 ${a_n\cdots a_1a_0}{(-k)}$ 表示 $\sum{i0}^n a_i(-k)^i$其中数位仍取自 ${0,1,\dots,k-1}$。例如 $12345_{(-10)}8265_{(10)}$。负底数进制的特别之处在于它可以在不需要负号的情况下表示负数。沿着同一思路还可以推广出复底数进制complex-base system如 $2\mathrm{i}$ 进制 quater-imaginary base以及用于表示实数 $\beta$ 展开$\beta$-expansion的非整数进位制non-integer base of numeration。混合基数进制每个数位有自己的基数标准进制中每个数位基数固定而混合基数进制允许每一位对应不同基数。最常见的应用就是计时小时用 24 进制分钟和秒用 60 进制。$a_n\cdots a_1a_0$ 在混合基数进制下表示的数为$$ \sum_{i0}^n a_i\prod_{j0}^{i-1}b_j $$其中 $b_j$ 为 $a_j$ 对应的基数。算法竞赛中最常见的混合基数进制是阶乘进制factorial number system记作 ${a_n\cdots a_1a_0}{~!}$表示的数为 $\sum{i0}^na_i i!$$a_i$ 对应基数 $i1$$0\leq a_i\leq i$由 $(n1)!-n!n\cdot n!$ 可知去除前导零后表示唯一。阶乘进制的典型应用是Lehmer 码 / 康托展开Cantor expansion用于排列排名与逆排名的双向映射详见 docs/math/permutation.md 的「排名」一节。仓库为阶乘进制提供了双向转换实现docs/math/code/base/base_1.cpp// --8-- [start:from_dec_factorial] 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; res.push_back(r 10 ? 0 r : A r - 10); } std::reverse(res.begin(), res.end()); return res; }// --8-- [start:to_dec_factorial] 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; }from_dec_factorial从基数 1 开始逐位递增baseto_dec_factorial则从 $n$ 递减——二者互为逆过程位 $i$ 恰好对应权 $i!$。C 中的进制字面量在 C 中非负整数用前缀数位后缀表示一个字面量数位与后缀均可为空。后缀用于声明字面量类型u/U表示unsignedl/L表示long等。各前缀规则如下前缀进制允许的数位示例0x/0X十六进制0-9,a-f,A-F0x1234ABCD为 $\text{1234ABCD}_{(16)}305~441~741$0八进制0-701234567为 $1234567_{(8)}342391$注意0本身也是八进制字面量1~9十进制0-9—0b/0BC14 起二进制0,10b11001010为 $11001010_{(2)}202$竞赛中常见的坑以0开头的字面量会被编译器当作八进制处理因此0123并不等于十进制 123若确实需要十进制0直接写0即可。延伸阅读进位制全章含证明与实现本文主体内容的完整来源含 Midy 定理证明、双射进制与阶乘进制的更多性质平衡三进制有符号位数进制的代表作含唯一性证明与 Topcoder 练习题格雷码反射二进制码的构造、正逆变换与汉诺塔等应用反码与补码补数法在计算机整数表示中的落地细节含反码/补码的数值范围对比Lehmer 码 / 康托展开阶乘进制在排列排名问题中的实战应用实现源码from_dec、to_dec、from_dec_bi、from_dec_factorial、to_dec_factorial五个函数的完整代码与自测断言。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考