进位制记数法

进位制记数法
术语名称	进位制记数法
英语名称	standard positional notation
别名	进制, 标准位值制, 标准记数法

基数
术语名称	基数
英语名称	radix
别名	base

进位制记数法(standard positional notation)，指一种位值制记数法中，每一个数位的位权依次是特定数（基数）的幂，且数位上的符号本身本身代表 0 到基数减一。也称进制/进位记数制。

按顺序排列这一类记数法下的数字，会呈现“满×进一”的形式，直到某一位数后续的所有位都“满”了会清空这些位并向前“进”位，因此被翻译为进（位）制。

尽管实际范围存在差异，位值制记数法常常默认指进位制记数法。不是进位制记数法的位值制记数法称为非标准位值制记数法。

定义

关于记数法

在位值制记数法中，若每一个数位上的位权都是某个大于 1 自然数 [math]\displaystyle{ r }[/math] 的幂，即 [math]\displaystyle{ \cdots,r^3,r^2,r,1,r^{-1},r^{-2},r^{-3},\cdots }[/math] ，且每一个数位上的数字都只使用 [math]\displaystyle{ r }[/math] 个符号 [math]\displaystyle{ 0,1,\cdots,r-1 }[/math] ，则称这一类记数法为进位制记数法(standard positional notation)，对应这一 [math]\displaystyle{ r }[/math] 的具体记数法称为 [math]\displaystyle{ r }[/math] 进制(base-[math]\displaystyle{ r }[/math] notation)，自然数 [math]\displaystyle{ r }[/math] 称为 [math]\displaystyle{ r }[/math] 进制中的基数(radix)/底数(base)。

关于数

对自然数 [math]\displaystyle{ r }[/math] ，集合 [math]\displaystyle{ D_r = \{0,1,2,\cdots,r-1\} }[/math] 是一个含有 [math]\displaystyle{ r }[/math] 个元素的符号集，记这一字符集合上的非空字符串集（或描述为 Kleene⁺ 闭包） [math]\displaystyle{ D_r^+ = \{d_n d_{n-1} d_{n-2} \cdots d_0 \mid n\gt =0 \land d_i \in D_r \} }[/math] ，通过等价关系 [math]\displaystyle{ d_n d_{n-1} d_{n-2} \cdots d_0 \sim 0 d_n d_{n-1} d_{n-2} \cdots d_0 }[/math] 定义的商集 [math]\displaystyle{ D_r^+/\sim }[/math] 与自然数集 [math]\displaystyle{ \mathbb{N} }[/math] 关于短先字典序序同构，其中元素称为 [math]\displaystyle{ r }[/math] 进制数。

记号

使用 [math]\displaystyle{ r\leq 16 }[/math] 的 [math]\displaystyle{ r }[/math] 进制时，通常在某一位数字上使用 [math]\displaystyle{ 0,1,\cdots,r-1 }[/math] 字符，并且按照类似平常十进制的方式书写。

整数排列为 [math]\displaystyle{ a_n a_{n-1} a_{n-2} \cdots a_0 }[/math] 的格式，用这一格式记录整数 [math]\displaystyle{ \sum_{i=0}^n a_i r^i = a_n r^n + a_{n-1} r^{n-1} + \cdots + a_0 }[/math] 。

反过来，每一位上的符号与数本身的递推关系满足：若 [math]\displaystyle{ m }[/math] 代表 [math]\displaystyle{ a_n a_{n-1} \cdots a_ 1 a_0 }[/math] ，则：

[math]\displaystyle{ \begin{aligned} m = q_0 r + a_0 &, 0 \leq a_0 \lt r, q_0 = \lfloor\tfrac{m}{r}\rfloor \\ q_0 = q_1 r + a_1 &, 0\leq a_1 \lt r, q_1 = \lfloor\tfrac{q_0}{r}\rfloor \\ q_1 = q_2 r + a_2 &, 0\leq a_2 \lt r, q_2 = \lfloor\tfrac{q_1}{r}\rfloor \\ \vdots \\ q_{n-1} = 0 r + a_n &, 0\leq a_n \lt r, q_{n-1} = \lfloor\tfrac{q_{n-1}}{r}\rfloor \\ \end{aligned} }[/math]

等式的右侧都是使用最小非负余数的带余除法。

小数部分

若带有小数部分，则可写为 [math]\displaystyle{ a_n a_{n-1} a_{n-2} \cdots a_0 . a_{-1} a_{-2} \cdots }[/math] ，用这一格式记录的数为 [math]\displaystyle{ \sum_{i=0}^n a_i r^i + \sum_{i=1}^\infty a_{-i} r^{-i}= a_n r^n + a_{n-1} r^{n-1} + \cdots + a_0 + a_{-1} r^{-1} + a_{-2} r^{-2} + \cdots }[/math] 。

进制标注

如果需要区分具体基数，通常有三种不同表示方法：

• 下标标注进制名称的缩写；
• 将数字打括号，并下标十进制标注进制基数；
• 在末尾加进制名称的缩写。

随着计算机特别是 C 语言风格的数字表示方法的普及， C 风格的前缀表示也逐渐常见，特别是在计算机语境中。

对于基数较大的情况，则需要约定符号表或者使用十进制书写每个数位上的数字。

常见进制

基数	名称	英文名称	缩写	字母后缀表示	C 风格前缀
2	二进制	binary	bin	B	0b
3	三进制	ternary, trinary
4	四进制	quaternary
5	五进制	quinary
6	六进制	senary, heximal, seximal
7	七进制	septimal, septenary
8	八进制	octal	oct	O	0,0o
9	九进制	nonary, nonal
10	十进制	decimal, denary	dec
12	十二进制	duodecimal, dozenal
16	十六进制	hexadecimal, sexadecimal, sedecimal	hex	H	0x
36	三十六进制	hexatrigesimal
60	六十进制	sexagesimal

此外， RFC 4648 中的 base16 、 base32 、 base64 也可以看成用进制命名的，参考对应条目。

记数系统
位值制记数法	进位制记数法/标准位值制记数法（进制）		二进制、八进制、十进制、十六进制、……
	非标准位值制记数法	带符号进位制记数法/ 平衡记数法（平衡进制）	平衡三进制、……
		双射记数法（双射进制）	一进制、双射十进制、双射二十六进制、……
		位权是幂 但基数不是自然数 （非自然数进制）	[math]\displaystyle{ -2 }[/math] 、 [math]\displaystyle{ -4 }[/math] 、……
			[math]\displaystyle{ \sqrt{2} }[/math] 、 [math]\displaystyle{ \sqrt{3} }[/math] 、 [math]\displaystyle{ \sqrt[12]{2} }[/math] 、……
			[math]\displaystyle{ 2i }[/math] 、 [math]\displaystyle{ \sqrt[4]{2}i }[/math] 、 [math]\displaystyle{ 2\omega }[/math] 、 [math]\displaystyle{ \sqrt[3]{2}\omega }[/math] 、 [math]\displaystyle{ -1\pm i }[/math] 、……
		位权不是幂（混合进制）	二五混合进制、阶乘进制、……
		其他	[math]\displaystyle{ p }[/math]-进数
			质数记数法、……
符值制记数法			罗马记数法、希腊记数法、……