我一直在阅读Donald Knuth的《编程艺术》第1卷,其中使用了MIX作为汇编语言。在Knuth谈到MIX中的算术运算的部分,我不明白减法、乘法和除法运算是如何进行的。
例如,课本上有这样的内容:
寄存器A具有以下字代码:
-| 1234 | 0 | 0 | 9
和存储单元,比如M,具有以下字代码:-| 2000 | 150 | 0
。
书中说在进行A-M时的结果是:+| 766 | 149|?
。
在MIX中,内存被拆分为多个单词。每个单词都有以下内容:第一个字段表示符号(+或-)
接下来的两个字节保存地址
下一个字节表示索引,而第五个字节用于字段规范
最后一个字节用于操作码
书中说在进行A-M时的结果是:+| 766 | 149|?
。
有人能帮我吗?
我们必须记住字节在MIX中的含义。字节必须能够容纳:
- 至少有64个不同的值,以及
- 最多100个不同值
在二进制计算机上,字节必须6位大。因为它允许我们存储2⁶=64个不同的值,满足条件1。64≤100,满足条件2。
在十进制计算机上,字节必须为两位数大。因为这将允许我们存储10²=100个不同的值,满足条件1。且100≤100,满足条件2。
让我们看看这些计算机是如何计算的。
在6位二进制计算机上:
┌─┬─┬─┬─┐ ┌─┬──────┬──────┬──────┐
│-│0│0│9│ would be represented as │-│000000│000000│001001│
└─┴─┴─┴─┘ └─┴──────┴──────┴──────┘
和
┌─┬─┬─┬─┐ ┌─┬──────┬──────┬──────┐
│-│150│0│ would be represented as │-│000010 010110│000000│
└─┴─┴─┴─┘ └─┴──────┴──────┴──────┘
将两者相减得到:
┌─┬──────┬──────┬──────┐
│+│000010 010101│110111│
└─┴──────┴──────┴──────┘
十进制等于:
┌─┬─┬─┬──┐
│+│149│55│ (we'll call this result A)
└─┴─┴─┴──┘
在2位十进制计算机上:
┌─┬─┬─┬─┐ ┌─┬──┬──┬──┐
│-│0│0│9│ would be represented as │-│00│00│09│
└─┴─┴─┴─┘ └─┴──┴──┴──┘
和
┌─┬─┬─┬─┐ ┌─┬──┬──┬──┐
│-│150│0│ would be represented as │-│01 50│00│
└─┴─┴─┴─┘ └─┴──┴──┴──┘
将两者相减得到:
┌─┬──┬──┬──┐
│+│01 49│91│
└─┴──┴──┴──┘
十进制等于:
┌─┬─┬─┬──┐
│+│149│91│ (we'll call this result B)
└─┴─┴─┴──┘
结论
我们注意到A≠B,但149总是存在的。不同的是最后一个字节。因此,根据MIX计算机使用的数字系统,最低有效字节将不同,而下面的两个字节将始终相同。因此,"在书中。
我意识到这个问题有点老了,但我最近正在解决这个问题。问题的核心是模棱两可;MIX的打印表示词语含糊不清。
根据Knuth的说法,一个字节必须至少包含64个值(0..63),并且不超过100(0..99)个值。仔细阅读规范(第125页TAOCP第1卷)
让我们用二进制和十进制的解释来解决这个问题。首先是MIX单词显式转换,然后以熟悉的方式执行运算十进制模式。最后,答案被转换回MIX表示。
BINARY MODE REALITY
1234 0 0 9 = [(1234 * 64^3) + (0 * 64*2) + (0 * 64) + 9] = 323485705
2000 150 0 = [(2000 * 64*3) + (150 * 64) + 0] = 524297600
-323485705 - -524297600 = 200811895
答案的MIX单词二进制表示为:
200811895 = [(766 * 64^3) + (149 * 64) + 55] = 766 149 55
现在进行十进制解释:
DECIMAL MODE REALITY
1234 0 0 9 = [(1234 * 10^3) + (0 * 10^2) + (0*10) + 9] = 1234009
2000 150 0 = [(2000 * 10^3) + (150 * 10) + 0] = 2001500
-1234009 - -2001500 = 767 491
MIX字的十进制表示为:
767491 = [(766 * 10^3) + (149 * 10) + 1] = 766 149 1
请注意,打印的表示不明确。例如CCD_ 5可以同时表示CCD_ 6或CCD_。根据你对单词的阅读(二进制或十进制模式)正在用两个独特的答案解决两个不同的问题。
下表将进行总结,希望能使事情变得清楚。
MIX Binary Decimal
rA -1234 0 0 9 -323485705 -1234009
SUB -2000 150 0 - -524297600 - -2001500
----------- ---------- --------
766 149 ? 200811895 767491 NOTE: 2 different answers!
如果打印的答案是766149?我们可以解决吗?价值
766 149 0 200811840 767490
? 55 1
MIX的单词表示足够模糊,不需要插入现场包装;这很容易出错。现场包装不相关因为运算是以整个单词为单位进行的。代表作为字段压缩字节的操作是另一个抽象层。
正在执行减法运算,因此人们会直观地认为答案应该是这样的:
rA - | 1234 | 0 | 0 | 9 | (before)
SUB - | 2000 | 150 | 0 |
---------------------------
| +766 | +150 | -9 | (after)
这是错误的,因为即使你知道(3:4)是150,(3:3)和(4:4)的单个值也无法确定。此外,字节的符号也不一致。如果考虑每字节5位的情况,机器会看到这个结果中最低有效字节为:
[321x(150)]-9=[321x(149)]+[320x(23)]
每字节有6位的机器会将其解释为:
[641x(150)]-9=[641x(149)]+[640x(55)]
更进一步,每字节7位的机器将把它解释为:
[1281x(150)]-9=[1281x(149)]+[1280x(119)]
因此,您可以从这些示例中看到,149对于任何字节大小都存在,但最低有效字节因机器而异。因此,正确答案是
rA - | 1234 | 0 | 0 | 9 | (before)
SUB - | 2000 | 150 | 0 |
--------------------------
rA + | 766 | 149 | ? | (after)
假设每个字节的大小为b
。因此+|1234|0|0|9
可以写成:-(1234*B³+9)
CCD_ 11可以写成:-(2000*B³+150*B+0)
现在从第一个数字减去第二个数字得到:-(1234*B³+9)-(-(2000*B³+150*B))
=766*B³+150*B-6
但这不能直接表示(因为术语是否定的),因此:=766*B³+149*B+(B-6)
其中B=2^b
因此,我们不知道寄存器的最后一个块将容纳什么,因为这取决于一个字节大小的定义,即b
。