Donald Knuth 的 Mix 汇编语言中的算术运算

Question

我一直在阅读 Donald Knuth 的《编程艺术》第一卷，其中使用 MIX 作为汇编语言。在Knuth讲MIX中算术运算的部分，我不明白减法、乘法和除法运算是如何进行的。

例如，课本上有这样的内容：

寄存器 A 具有以下字代码：-| 1234 | 0 | 0 | 9且存储器单元（例如 M）具有以下字代码：-| 2000 | 150 | 0。

书上说执行 AM 的结果是：+| 766 | 149|?。

在 MIX 中，内存被分成单词。每个字具有以下内容： 第一个字段表示符号（+ 或 -）
接下来的两个字节保存地址。
下一个字节表示索引，而第五个字节用于字段规范。
最后一个字节用于操作码。
书上说执行 AM 的结果是：+| 766 | 149|?。

谁能帮我这个？

Answer 1

我们必须记住MIX 中字节的含义。一个字节必须能够容纳：

\n

\n
1. 至少 64 个不同的值，并且
\n
2. 最多 100 个\n不同的值
\n

\n

在二进制计算机上，字节必须为6 位大。因为它允许我们存储 2\xe2\x81\xb6=64 个不同的值，满足条件 1。 和 64\xe2\x89\xa4100，满足条件 2。

\n

在十进制计算机上，字节必须是2 位数字大。因为这将允许我们存储 10\xc2\xb2=100 个不同的值，满足条件 1。以及 100\xe2\x89\xa4100，满足条件 2。

\n

让我们看看每台计算机上的计算是如何完成的。

\n

在 6 位二进制计算机上：

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x90                           \xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82-\xe2\x94\x820\xe2\x94\x820\xe2\x94\x829\xe2\x94\x82   would be represented as \xe2\x94\x82-\xe2\x94\x82000000\xe2\x94\x82000000\xe2\x94\x82001001\xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x98                           \xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

和

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x90                           \xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82-\xe2\x94\x82150\xe2\x94\x820\xe2\x94\x82   would be represented as \xe2\x94\x82-\xe2\x94\x82000010 010110\xe2\x94\x82000000\xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x98                           \xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

将两者相减得出：

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82+\xe2\x94\x82000010 010101\xe2\x94\x82110111\xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

以十进制表示等于：

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82+\xe2\x94\x82149\xe2\x94\x8255\xe2\x94\x82  (we'll call this result A)\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

在 2 位十进制计算机上：

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x90                           \xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82-\xe2\x94\x820\xe2\x94\x820\xe2\x94\x829\xe2\x94\x82   would be represented as \xe2\x94\x82-\xe2\x94\x8200\xe2\x94\x8200\xe2\x94\x8209\xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x98                           \xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

和

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x90                           \xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82-\xe2\x94\x82150\xe2\x94\x820\xe2\x94\x82   would be represented as \xe2\x94\x82-\xe2\x94\x8201 50\xe2\x94\x8200\xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x98                           \xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

将两者相减得出：

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82+\xe2\x94\x8201 49\xe2\x94\x8291\xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n

以十进制表示等于：

\n

\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x82+\xe2\x94\x82149\xe2\x94\x8291\xe2\x94\x82  (we'll call this result B)  \n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n\n

结论

\n

我们注意到 A\xe2\x89\xa0B，但 149 始终存在。不同的是最后一个字节。\n因此，根据 MIX 计算机使用的数字系统，最低有效字节会有所不同，而接下来的两个字节将始终相同。因此，“？” 在书里。

\n

Answer 2

正在执行减法运算，所以人们直观地认为答案应该是这样的：

rA  - | 1234 | 0 | 0 | 9  | (before)
SUB - | 2000 |  150  | 0  |
---------------------------
      | +766 |  +150 | -9 | (after)

这是错误的，因为即使您知道 (3:4) 是 150，也无法确定 (3:3) 和 (4:4) 各自的值。此外，字节的符号不一致。如果考虑每字节 5 位的情况，机器会将此结果中的最低有效字节视为：

[ 32 ¹ x (150) ] - 9 = [ 32 ¹ x (149) ] + [ 32 ⁰ x (23) ]

每字节 6 位的机器会将其解释为：

[ 64 ¹ x (150) ] - 9 = [ 64 ¹ x (149) ] + [ 64 ⁰ x (55) ]

更进一步，每字节 7 位的机器会将其解释为：

[ 128 ¹ x (150) ] - 9 = [ 128 ¹ x (149) ] + [ 128 ⁰ x (119) ]

因此，您可以从这些示例中看到，任何字节大小都存在 149，但最低有效字节因计算机而异。因此，正确答案是

rA  - | 1234 | 0 | 0 | 9 | (before)
SUB - | 2000 |  150  | 0 |
--------------------------
rA  + |  766 |  149  | ? | (after)