4

我一直在阅读 Donald Knuth 的 The Art of Programming, Volume 1，其中将 MIX 用作汇编语言。在 Knuth 谈到 MIX 中的算术运算的部分中，我不明白减法、乘法和除法运算是如何进行的。

例如，教科书有这样的：

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

书中说执行 AM 的结果是：+| 766 | 149|?.

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

谁能帮我这个？

4

4 回答 4

5

我们必须记住字节在 MIX 中的含义。一个字节必须能够保存：

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

在二进制计算机上，字节必须是6 位大。因为它允许我们存储 2⁶=64 个不同的值，满足条件 1。并且 64≤100，满足条件 2。

在十进制计算机上，字节必须是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 计算机使用的数字系统，最低有效字节会有所不同，而后面的两个字节将始终相同。因此“？” 在书里。

于 2021-02-14T16:08:44.400 回答
4

我意识到这个问题有点老了，但我最近正在解决这个问题。问题的核心是模棱两可。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

请注意，打印的表示是模棱两可的。eg1234 0 0 9可以同时表示323485705或1234009。根据您对单词的阅读（二进制或十进制模式），您正在解决两个不同的问题和两个独特的答案。

下表将总结并希望使事情变得清晰。

       MIX            Binary           Decimal
rA  -1234 0 0 9    -323485705         -1234009
SUB -2000 150 0  - -524297600       - -2001500
    -----------    ----------         --------
      766 149 ?     200811895           767491 NOTE: 2 different answers!

鉴于打印的答案是 766 149 ？我们可以解决吗？价值。

  766 149 0     200811840           767490
          ?            55                1

MIX 词的表示足够模糊，无需在字段中打包；这很容易出错。字段打包不相关，因为操作将整个单词作为一个单元进行。将操作结果表示为字段打​​包字节是另一层抽象。

于 2019-03-01T00:51:20.220 回答
3

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

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

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

[ 32 1 x (150) ] - 9 = [ 32 1 x (149) ] + [ 32 0 x (23) ]

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

[ 64 1 x (150) ] - 9 = [ 64 1 x (149) ] + [ 64 0 x (55) ]

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

[ 128 1 x (150) ] - 9 = [ 128 1 x (149) ] + [ 128 0 x (119) ]

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

rA  - | 1234 | 0 | 0 | 9 | (before)
SUB - | 2000 |  150  | 0 |
--------------------------
rA  + |  766 |  149  | ? | (after)
于 2015-04-14T15:36:58.510 回答
3

假设每个字节的大小为b。因此+|1234|0|0|9可以写成：
-(1234*B³+9)
，-|2000|150|0|也可以写成：
-(2000*B³+150*B+0)。
现在从第一个数中减去第二个数得到：
-(1234*B³+9)-(-(2000*B³+150*B))
=766*B³+150*B-6
但这不能直接表示（因为一个项是负数），因此：
=766*B³+149*B+(B-6) Where B=2^b。

因此我们不知道寄存器的最后一个块将保存什么，因为这取决于一个字节大小的定义，即b.

于 2017-08-26T08:55:08.203 回答