2i进制,是由高德纳于1995年提出来的,当时用作高中科学精英研究用。它是一种以2i为基数的非标准进位制。这种进制以0、1、2、3为基本數碼[1],能够独一无二的表示全体复数。
转换2i进制到十进制
2i的冪 k | (2i)k |
-5 | −1/32i |
-4 | 1/16 |
-3 | 1/8i |
-2 | −1/4 |
-1 | −1/2i |
0 | 1 |
1 | 2i |
2 | −4 |
3 | −8i |
4 | 16 |
5 | 32i |
6 | −64 |
7 | −128i |
8 | 256 |
2i的冪
将2i进制转换为十进制可以用标准公式。这个公式是:
进制数
的十进制数为
![{\displaystyle \cdots +d_{3}\cdot b^{3}+d_{2}\cdot b^{2}+d_{1}\cdot b+d_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5443e79b16a5a949a6273d7050e13a58f3d435e3)
2i进制中,
。
示例
将
转换为十进制,可按照上述公式填入相应数字:
![{\displaystyle 1\cdot (2i)^{3}+1\cdot (2i)^{2}+0\cdot (2i)^{1}+1\cdot (2i)^{0}=-8i-4+0+1=-3-8i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad0ae7ec9052c96758b8b1547a728537ec0babbc)
再比如:
十进制是
![{\displaystyle 1\cdot (2i)^{6}+3\cdot (2i)^{4}+3\cdot (2i)^{0}=-64+3\cdot 16+3=-13}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf6786f7c178bcb597cfa33b7c88931f5aad072e)
十进制转换到2i进制
也能将十进制数转换为2i进制。 每个复数(形如a+bi) 都有个2i进制形式。 大多十进制数都只有1个形式,但像1这样的数在十进制中有两种形式1.0 = 0.9, 相对应的 1/5有两种2i进制形式:1.03002i = 0.00032i。
要转换十进制数,先将实部和虚部分别转换为2i进制数,然后加到一起即可。 比如, –1+4i 等于–1 加上 4i,–1的2i进制数是103, 4i的2i进制数是20,因此 –1+4i = 1232i。
转换虚部时,可以先乘以2i,得到一个实数;然后将这个实数转换为2i进制,然后右移一位即可(等效于除以 2i)。 例如,虚部是 6i,先将6i 乘以2i 得到 –12,化为2i进制是3002i,然后右移一位,得到: 6i = 302i。
转换实数,可以用方程组来求解。
示例:实数
我们来求解7的2i进制数。我们很难知道这个2i进制数有多长,所以我们先假设一个比较长的数。 我们先选六位试试,如果不够,我们再延长。 我们写出公式,然后分组:
![{\displaystyle {\begin{aligned}7_{10}&=d_{0}+d_{1}\cdot b+d_{2}\cdot b^{2}+d_{3}\cdot b^{3}+d_{4}\cdot b^{4}+d_{5}\cdot b^{5}\\&=d_{0}+2id_{1}-4d_{2}-8id_{3}+16d_{4}+32id_{5}\\&=d_{0}-4d_{2}+16d_{4}+i(2d_{1}-8d_{3}+32d_{5})\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f18796a3c84ae43b67abd4b1240898a99cc745ad)
7是实数,因此d1、d3 和 d5 是0。 剩下就是系数d0、d2 和 d4。 因为 d0 − 4 d2 + 16 d4 = 7 并且他们只能是 0、 1、 2 或 3 。可能的结果是: d0 = 3, d2 = 3 , d4 = 1。 这样就找到了710的2i进制数。
![{\displaystyle {\begin{aligned}7_{10}=010303_{2i}=10303_{2i}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/502cfb75ec0cfee168c495881f5d050bcbff8d0b)
示例: 虚数
找一个纯虚数的2i进制数,可以模拟实数的方法。 例如6i, 也可以用公式。实部全为零,虚部化为6。 6i 很容易看出 d1 = 3 其他各位都是0。6i就是:
![{\displaystyle {\begin{aligned}6i_{10}=30_{2i}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/905765b33c36fdf243e3a52eb251208a7522e523)
其他的轉換方式
對實數而言,2i进制表示法實際上與負四进制相同。要將複數x+iy轉換成2i进制可以透過將x和y/2分別轉換為負四进制再將之交錯合併來完成轉換成2i进制的工作。如果x和y都是有限的二进制小數,則可以使用連續的带余除法來將十进制數轉換成2i进制:
例如:35+23i=121003.22i
35 23i/2i=11.5 11=12−0.5
35÷(−4)=−8, 餘 3 12/(−4)=−3, 餘 0 (−0.5)×(−4)=2
−8÷(−4)= 2, 餘 0 −3/(−4)= 1, 餘 1
2÷(−4)= 0, 餘 2 1/(−4)= 0, 餘 1
20003 + 101000 + 0.2 = 121003.2
32i+16×2−8i−4×0+2i×0+1×3−2×i/2=35+23i
小数点“.”
十进制中小数点用来区分整数部分和小数部分。2i进制中小数点一样可以用,比如
中,小数点用来分割b的正数幂和負数幂。带小数点时,公式是:
![{\displaystyle d_{5}b^{5}+d_{4}b^{4}+d_{3}b^{3}+d_{2}b^{2}+d_{1}b+d_{0}+d_{-1}b^{-1}+d_{-2}b^{-2}+d_{-3}b^{-3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2684b2ec54ca283523079ca7982c856740837998)
或
![{\displaystyle 32id_{5}+16d_{4}-8id_{3}-4d_{2}+2id_{1}+d_{0}+{\frac {1}{2i}}d_{-1}+{\frac {1}{-4}}d_{-2}+{\frac {1}{-8i}}d_{-3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2a6f75e0e277bdea6f29e45c7a494fbea0e92ee)
示例
將i轉換為2i進制,没有小数点的话,可能没办法做到。因此:
![{\displaystyle {\begin{aligned}i&=32id_{5}+16d_{4}-8id_{3}-4d_{2}+2id_{1}+d_{0}+{\frac {1}{2i}}d_{-1}+{\frac {1}{-4}}d_{-2}+{\frac {1}{-8i}}d_{-3}\\&=i(32d_{5}-8d_{3}+2d_{1}-{\frac {1}{2}}d_{-1}+{\frac {1}{8}}d_{-3})+16d_{4}-4d_{2}+d_{0}-{\frac {1}{4}}d_{-2}\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a0e23bdf96f580ad008ca67aacfa89a1e13d143)
因為实部为0,故 d4 = d2 = d0 = d-2 = 0。
接著考慮虚部部分,当 d5 = d3 = d -3 = 0 并且 当 d1=1 , d-1=2 时结果正确。所以
.
示例(分數)
將
轉換為2i進制,其結果為-0.0203。
加减法
2i进制也可以做加减法。 首先要记住以下规则:
- 数字超过3时, 减 4 "进" −1 到左边第二位。
- 数字小于0时, 加 4"进" +1 到左边第二位。
简单的说: 「加四进一、减四借一」(當作四進制來計算)。 和一般竖式加法不同的是,要借/进到左边第二位。
示例:加法
1 - 2i 1031 3 - 4i 1023
1 - 2i 1031 1 - 8i 1001
------- + <=> ----- + ------- + <=> ----- +
2 - 4i 1022 4 - 12i 12320
第一个例子,先是1+1=2。然后是3+3=6,6比3大,我们得减4借1。接着是0+0=0。然后是1+1=2,在减去借的1。得1。
第二个例子,先是3+1=4; 4 比3大,我们得减4借1。然后是2+0=2。 接着是0+0=0,再减去借位1,得-1,小于0,我们得加四进一。 然后是1+1=2; 最后是进位1。我们得到结果
。
示例:减法
减法和加法类似。下面是例子:
- 2 - 8i 1102
1 - 6i 1011
------- - <=> ----- -
- 3 - 2i 1131
这个例子中,先是2-1 = 1。 然后是0-1=-1,小于0,加4进1得3;接着是1-0=1。然后是1-1=0,加上进位得1。 结果就是
。
乘法
乘法也要用到上面两点。先逐位相乘,然后叠加。比如:
11201
20121 x
--------
11201 <--- 1 x 11201
12002 <--- 2 x 11201
11201 <--- 1 x 11201
00000 <--- 0 x 11201
12002 + <--- 2 x 11201
------------
120231321
也就是
。
查表转换
下面是一个常用的复数对照表。我们可以用叠加的方法来转换复数
十进制 | 2i进制 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 10300 | 5 | 10301 | 6 | 10302 | 7 | 10303 | 8 | 10200 | 9 | 10201 | 10 | 10202 | 11 | 10203 | 12 | 10100 | 13 | 10101 | 14 | 10102 | 15 | 10103 | 16 | 10000 | | 十进制 | 2i进制 | −1 | 103 | −2 | 102 | −3 | 101 | −4 | 100 | −5 | 203 | −6 | 202 | −7 | 201 | −8 | 200 | −9 | 303 | −10 | 302 | −11 | 301 | −12 | 300 | −13 | 1030003 | −14 | 1030002 | −15 | 1030001 | −16 | 1030000 | | 十进制 | 2i进制 | 1i | 10.2 | 2i | 10.0 | 3i | 20.2 | 4i | 20.0 | 5i | 30.2 | 6i | 30.0 | 7i | 103000.2 | 8i | 103000.0 | 9i | 103010.2 | 10i | 103010.0 | 11i | 103020.2 | 12i | 103020.0 | 13i | 103030.2 | 14i | 103030.0 | 15i | 102000.2 | 16i | 102000.0 | | 十进制 | 2i进制 | −1i | 0.2 | −2i | 1030.0 | −3i | 1030.2 | −4i | 1020.0 | −5i | 1020.2 | −6i | 1010.0 | −7i | 1010.2 | −8i | 1000.0 | −9i | 1000.2 | −10i | 2030.0 | −11i | 2030.2 | −12i | 2020.0 | −13i | 2020.2 | −14i | 2010.0 | −15i | 2010.2 | −16i | 2000.0 | |
示例
![{\displaystyle 5=16+(3\cdot -4)+1=10301_{2i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/959d4876cd0dceb0b6b281f10b6e0dd052c23ca2)
![{\displaystyle i=2i+2\left(-{\frac {1}{2}}i\right)=10.2_{2i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f38245a76da69b37a10eed70e32e09c8c56db27)
![{\displaystyle 7{\frac {3}{4}}-7{\frac {1}{2}}i=1(16)+1(-8i)+2(-4)+1(2i)+3\left(-{\frac {1}{2}}i\right)+1\left(-{\frac {1}{4}}\right)=11210.31_{2i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bde4b250101ec3d6e04818dd47ccf937c8fe1893)
参见
- 四進制
- 十六進制
- 複進制(英语:Complex base systems)
- 负进制(英语:Negative base)
参考资料
- D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"
^ Donald Knuth. An imaginary number system. Communications of the ACM. April 1960, 3 (4).
|
---|
| 著作 | - 《计算机程序设计艺术》
- 《歌曲的計算複雜度(英语:The Complexity of Songs)》
- 《電腦與排版(英语:Computers and Typesetting)》
- 《具體數學》
- 《超現實數(英语:Surreal Numbers (book))》
- 《計算機科學家很少談論的事情(英语:Things a Computer Scientist Rarely Talks About)》
- 論文選集(英语:Selected papers series of Knuth)
|
---|
| 软件 | - TeX
- METAFONT
- MIXAL
- MIX(英语:MIX (abstract machine))
- MMIX(英语:MMIX)
|
---|
| 字型 | |
---|
| 文学编程 | |
---|
| 算法 | - X算法
- 高德納-本迪克斯補全算法(英语:Knuth–Bendix completion algorithm)
- KMP算法
- 高德納洗牌算法(英语:Fisher–Yates shuffle)
- RSK 對應(英语:Robinson–Schensted–Knuth correspondence)
- TPK算法(英语:TPK algorithm)
- 概念化戴克斯特拉算法
- Knuth's Simpath algorithm(英语:Knuth's Simpath algorithm)
|
---|
| 相關 | - 舞蹈链
- 高德納獎勵支票(英语:Knuth reward check)
- 高德納獎
- 高德納箭號表示法
- 编译器递归测试
- 2i進制
- -yllion(英语:-yllion)
- 《普茨比度量衡体系(英语:Potrzebie#System of measurement)》
|
---|
|