摘要生成中...
AI 摘要
Hunyuan-lite
本文由本地笔记迁移而来

笔记创建于 240321，于 260606 迁移，并增补整理文章。

整数的表示

定理：令 b 是一个大于 1 的整数。则如果 n 是一个正整数，就可以唯一地表示为下面的形式：

n=akbk+ak−1bk−1+⋯+a1b+a0n=a_{k}b^k+a_{k-1}b^{k-1}+\dots+a_{1}b+a_{0}
可记为 (akak−1……a1a0)b(a_{k}a_{k-1}\dots\dots a_{1}a_{0})_{b}。其中十进制的下标 10 可以省略。

  • 二进制展开式只使用 0 和 1 这两个数字。
  • 八进制展开式使用数字{0,1,2,3,4,5,6,7}.
  • 十六进制使用数字{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. 字母 A 到 F 代表十进制数字 10 到 15

二进制数字表示法：考虑一个形如 bmbm−1…b1b0.b−1b−2…b−n−1b−nb_{m}b_{m-1}\dots b_{1}b_{0}.b_{-1}b_{-2}\dots b_{-n-1}b_{-n} 的数字，定义：

b=∑i=−nm2i×bib=\sum_{i=-n}^m 2^i\times b_{i}

image.png

十进制数转任意进制

构造整数 n 的 b 进制展开式（基数乘除法）：

  1. n 除以 b，得到商和余数。n=bq0+a0,0≤a0<bn = bq_0 + a_0, 0 ≤ a_0 < b。数 a0a_0 是 n 的 b 进制展开式中最右边的数字。
  2. q0q_0 除以 b。q0=bq1+a1,0≤a1<bq_0 = bq_1 + a_1, 0 ≤ a_1 < b。余数 a1a_1 是 n 的 b 进制展开式中从右边开始的第二个数字。
  3. 继续将商依次除以 b，得到 b 进制的余数。当商为 0 时，进程终止。

该过程从右向左产生 n 的 b 进制数字。

image.png

任意一个二进制小数都可以用十进制小数表示。

总结：

  • 整数部分除以基取余，最先取得的余数为最低位
  • 小数部分乘基取整，最先取得的整数为最高位
  • 最后结果拼接

理解方法详见我的博客文章：【刷题日记】算法题常用数学算法和技巧 | 半方池水半方田

二进制、八进制、十六进制

image.png

  • 每个八进制数字对应一组三位二进制数字
  • 每个十六进制数字对应一组四位二进制数字

二进制转八进制或十六进制总结：以小数点为界

  • 整数部分从小数点往左，一组一组分，高位补零
  • 小数部分从小数点往右，一组一组分，低位补零

平衡三进制

平衡三进制，也称为对称三进制。这是一个广义进位系统。

正规的三进制的数字都是由 0,1,2 构成的，而平衡三进制的数字是由 -1,0,1 构成的。它的基数也是 3（因为有三个可能的值）。

10 进制转换为平衡三进制的过程：在平衡三进制的转转换法中，需要先写出一个给定的数 n 在标准三进制中的表示。当 n 是用标准三进制表示时，其数字的每一位都是 0、1 或 2。从最低的数字开始迭代，我们可以先跳过任何的 0 和 1，但是如果遇到 2 就应该先将其变成 -1，下一位数字再加上 1。而遇到数字 3 （被进位的情况）则应该转换为 0 下一位数字再加上 1。

Python 的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
def _decimal_to_balanced_ternary(self, n):
	"""辅助函数：将十进制 1-12 转换为 3 位平衡三进制元组（高位在前）"""
	res = []
	for _ in range(3):
		rem = n % 3
		if rem == 2:
			res.append(-1)
			n = (n + 1) // 3
		else:
			res.append(rem)
			n = n // 3
	return tuple(res[::-1])

本文参考

  • 研究生课程《离散数学》数论与密码学部分
  • 《CSAPP》相关内容
  • 王道 408 考研笔记思维导图解耦
  • 平衡三进制 - OI Wiki