5

是否可以仅使用 AND、OR 和 NOT 运算符编写逻辑来比较 2 个操作数并在不使用跳转的情况下返回 true/false (-1, 0)？如果是这样，您能否给我一些提示，因为这对我来说似乎是不可能的。我正在尝试用“计算系统的元素”一书的汇编语言来实现 eq、lt 和 gt 。

4

7 回答 7

6

如果您仅使用按位逻辑运算符，并且在进位丢失的位置加/减，则不可能从比较操作中获得 -1 或 0（或 1 或 0，就此而言）的结果：

  • 对于按位运算符，结果的第n位仅取决于两个操作数的第n位。

  • 对于加法，请考虑二进制加法的工作原理：结果的第n位可能受每个操作数的第n位和第n位右侧的位（通过进位）的影响；但不受操作数中位n左侧的任何位的影响。（你可以认为这是对两个偶数相加不能得到奇数结果的观察的概括。）

  • 由于单个加法或按位运算不能将任何信息从操作数的第n位左侧传播到结果的第n位，因此任何加法或按位运算的组合也不能；减法（假设这里是 2 的补码）可以被认为是这样的组合：xy = x+(NOT y)+1。

所以你不能得到 0 的结果 2==2，但 -1（或 1） 2==4，例如：所需结果的位 0 在每种情况下都是不同的，但结果只能取决于在两个操作数的第 0 位上，在每种情况下都是相同的。

如果您的真假值仅在顶部（即最左边）位不同，则可以完成。

例如，使用 8 位值：使用 0x80 表示真，使用 0 表示假；那么x == y可以实现为(NOT((x - y) OR (y - x))) AND 0x80.

如果将可用操作扩展为包括右移，或者如果 ADD 操作可以产生一个进位，该进位可以添加回结果的底部，则可以解决最初所述的问题。

于 2010-01-22T01:12:38.383 回答
2 
XOR a, b

如果 a 和 b 相等，则为 0，否则为非零。

SUB a, b
AND a, SIGN_BIT

（其中 SIGN_BIT 是删除除...符号位之外的所有内容的掩码）

如果 a 大于 b 将导致零，如果 a 小于或等于 b 将导致非零（假设 2 的完整性）。

于 2010-01-21T22:01:31.523 回答
1

以防万一这是一个纯理论问题：由于您正在对一组有限的操作数进行操作，因此所有可能的函数都可以仅使用 OR、AND 和 NOT 来表示。

更多解释见析取范式。

出于实际目的，匿名回答更有用:-) ...

编辑：即使我的理论答案也可能不正确：对这个问题应用析取范式需要移位操作，因为输出字的每一位都取决于输入位的所有位。我还没有弄清楚如何使用 AND、OR、NOT 和算术来实现移位（我不确定这是否可能......）

我留下了这篇文章，但作为过早回答的负面例子......

于 2010-01-21T22:05:58.870 回答
1

A Equal B 可以用 xor 表示： 

(A AND (NOT B)) OR ( A AND (NOT B))

如果 A==B 则输出 0 ，如果不是则输出 != 0

对于小于 B 的 A，您可以使用 (A - B AND SIGN_MASK)

，其中 SIGN_MASK 屏蔽除符号位之外的所有内容，将为您提供 MAX_NEGATIVE_INTEGER 的真值和 0 的假值。

大于可以简单地从小于构造

于 2010-01-21T22:14:41.087 回答
0

我们正在阅读同一本书，只是遇到了这个问题。

我们能找到的最佳解决方案是生成唯一标签，然后使用 JEQ 命令跳转到预期的标签，然后在完成后跳转到更下方的标签。

伪代码：

if they're equal, jump to EQUAL

// not equal section
push constant false
jump to DONE

// equal section
(EQUAL)
push constant true

// done section
(DONE)

以下是我们具体实现的方式（在 Ruby 中）。

于 2012-05-28T05:50:53.813 回答
-1

从历史的某个时间点开始，x86 CPU 就具有“条件移动”操作。

于 2010-01-21T22:08:30.617 回答
-1

您正在谈论的汇编语言中的所有算术运算都可能基于运算结果（= 0？和> 0？）进行条件跳转，可用于获得所需的布尔结果。

于 2010-01-30T12:25:07.493 回答