唐纳德高德纳的 Mix 汇编语言中的算术运算



我一直在阅读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中的含义。字节必须能够容纳:

  1. 至少有64个不同的值,以及
  2. 最多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

相关内容

  • 没有找到相关文章

最新更新