我正在为一个挑战写一个程序的小人电脑:
这个程序应该接受一个十进制数作为输入,并输出等价的二进制数.它应该重复地将输入除以2,然后输出二进制数。
例如,如果输入是8,机器应该将8除以2并输出0。然后,它应该将4除以2并输出0。接下来,它应该将2除以2并输出0。最后,它应该将1除以2并输出1。
下面是我的代码:
INP
STA NUM
LDA 0
STA REMAIN
LOOP LDA NUM
SUB TWO
BRP CONTINUE
BRA END
CONTINUE LDA REMAIN
ADD ONE
STA REMAIN
BRA LOOP
END LDA REMAIN
OUT
HLT
NUM DAT
REMAIN DAT
ONE DAT 1
TWO DAT 2
问题
当我用输入8运行这个程序时,它一直在循环。当调试时,我看到REMAIN
没有像我预期的那样初始化为0,而是初始化为901。那么我还是不明白为什么这会导致一个无限循环,因为我反复减去2,在某个点上,这会导致一个负数。但不知何故,这种情况从来没有发生过。
我错在哪里?
2条答案
按热度按时间svmlkihl1#
您已经描述了一个算法,该算法将以二进制表示形式输出一个数字,反转(!)。我会假设这是你想要实现的。
在您的尝试中有几个问题:
LDA 0
将加载邮箱0中的值,这不是您想要的。相反,将邮箱标记为ZERO
并将其初始化为值0,然后执行LDA ZERO
。REMAIN
是一个误导性的名称,因为您的代码不会在那里存储余数,而是除以2的商。余数是重复减去2后在NUM
中剩余的部分。我会使用标签QUOTIENT
或HALF
代替。REMAIN
的最终输出不是余数,而是商。由于只想输出0或1,因此输出应该依赖于NUM
,而不是REMAIN
。NUM
,所以用2相减的结果会丢失,循环的下一次迭代将从NUM
的原始值重新开始,并再次做完全相同的事情,当NUM
为2或更大时,会导致无限循环。在CONTINUE
标签上应该有一个STA NUM
。NUM
是奇数或偶数的情况之间没有区别。唯一被捕获的事件是当减法导致负溢出时,但此时您不知道是输出0还是1。您应该添加一条BRZ
指令来检测NUM
为零的情况,这样您就知道需要输出0。另一种情况,当输出1时,将由负溢出识别。NUM
值的一半)并将其用作NUM
来重复整个过程。这应该继续下去,直到商为零。下面是你的代码,其中考虑了所有这些注解:
你可以在这里运行它。它将默认为输入41(作为示例),其输出将为:
同样,这是 * 反向 * 二进制,所以0 b101001,即。32 + 8 + 1
最后一点,这不是最有效的算法,因为减法的次数将是𝑛/2 +𝑛/4 +𝑛/8 +...= O(𝑛)。𝑛如果你使用2的幂减法,而不是总是2,这可以在O(log)的时间复杂度内完成。这将以更复杂的程序为代价。
piwo6bdm2#
这里有一些关于你发布的代码的基本提示。
LDA 0
不做你想做的事:它将0视为地址,因此从存储器位置0加载(实际上存储代码而不是数据;这里它保存第一个指令INP
,其值为901,因此def不是0。您需要使用值为0的基准面,就像SUB TWO
-LDA ZERO
一样,并与其他常量一起沿着定义ZERO DAT 0
。NUM
中减去,需要一个加载-减去-* 存储 * 序列。由于您没有存储回NUM
,NUM
永远不会改变-因此在load & subtract之后放置一个STA NUM
,就像使用REMAIN一样此外,本发明还
LDA 0
没有将0加载到累加器中,而是901 -所以只有3条指令进入程序,我们有一些意想不到的事情。