ARM汇编谜题

Question

首先，我不确定是否存在解决方案。我花了几个小时尝试想出一个解决方案，所以请注意。

问题如下：

r1 包含任意整数，标志不根据其值设置。只使用两个指令，如果 r1 为 0x80000000，则将 r0 设置为 1；否则将 r0 设置为 0。

在三个指令中很容易做到这一点（有许多方法），然而在两个指令中实现似乎非常困难，甚至可能是不可能的。

- Ivan Tarasov

---

架构版本有任何限制吗？这可能会影响是否存在解决方案。 - Michael Madsen

现在对我来说更多是好奇的问题，不涉及实际应用，所以任何架构都可以。 - Ivan Tarasov

在过去的一天里，我思考了很多次关于这个问题，我非常有信心地说这是不可能的。有许多方法可以用3条指令实现，但按照要求，我想不出用2条指令完成的方法。 - Dan

Answer 1

something like

SMMUL r0,r1,r1
MOV r0,r0,lsr #30

- Martin

---

好的回答，SMMUL有四个操作数，对吗？也许是SMMUL r2，r0，r1，r1。我认为如果r1的最高位设置了，r0最终会变成1、2或3。 - old_timer

Arm的文档将SMMUL描述为有符号的顶部字乘法，因此将其列为3个寄存器操作码。我的想法是：0x80000000 x 0x80000000.在顶部字中给出0x40000000，因此30位移位将把该bit30带到bit0。（这里没有arm V6架构来测试） - Martin

@dwelch：你想的是SMULL。SMMUL是一条ARMv6指令，只提供结果的前32位。 - Mike Seymour

谢谢，知道了。无论如何，你的结果的前两位可以是1、2或3，取决于r1中的其他位，你仍然需要第三条指令将这两个较低的位或起来得到结果。 - old_timer

@dwelch：将有符号数平方得到的最大结果是（-2^31）^2 = 2 ^ 62; 除了0x80000000之外的任何值都会给出一个更小（且非负）的结果。在您的4位示例中，您正在进行无符号乘法; 有符号乘法将把0xF解释为-1，从而得出0x01的结果。因此，这两个指令确实给出了正确的结果，不需要第三个指令。 - Mike Seymour

Answer 2

这里有一个部分解决方案，可以在r0的最高位给出正确答案，因此它可以作为移位操作数使用(r0 lsr #31)。

; r0 = r1 & -r1
rsb r0, r1, #0
and r0, r0, r1

这是因为当 0 和 0x80000000 取反时，它们保留了它们的符号位。我相当确定没有精确的解决方案。

编辑：不，这不是不可能的。请参见 Martin 的回答。

- Mike Seymour

---

漂亮的技巧使用了否定。不幸的是，提取最高位需要第三条指令（或者修改使用结果的指令，但这并不总是可行的）。 - Ivan Tarasov

我整天都在思考这个问题，我确信两条指令的解决方案也是不可能的。 - Nils Pipenbrinck

Answer 3

adds  r0, r1, #0x80000000 ; if r1 is 0x80000000, r0 will now hold 0
movne r0, #1              ; otherwise, set r0 to 1

这相当于：

unsigned int r0, r1;
r0 = r1 + 0x80000000; // 32 bits, so top bit will be lost on overflow
if (r0 != 0)
{
    r0 = 1;
}

- Eric Miller

---

你颠倒了结果：问题规范要求当r1==0x80000000时，r0中应为1，否则为0，而你在r1==0x80000000时将r0设置为0，在其他情况下将其设置为1，这是一个简单得多的问题（这是完成任务的方法之一，只需3条指令）。 - Ivan Tarasov

Answer 4

类似这样：

mov r0,r1,lsr #31

- old_timer

---

只要r1的高位设置了，这将把r0设置为1。但这不是OP所要求的。 - Michael Madsen

啊，我明白了，我看的是位而不是值。 - old_timer

Answer 5

如果想使用“快速”指令，这是一个棘手的难题。我无法想出解决方案，但可以提供几个更多的“概念”：

; 如果目标是在$80000000时具有零值，否则具有其他值：
  adds r0,r1,r1 ; 只有在$80000000时才会溢出
  movvc r0,#whatever

; 如果目标是在$80000000时具有$80000000的值，否则为零
  subs r0,r1,#0  ; 只有在$80000000时才会溢出
  movvc r0,#0 ; 或者其他任何值
; 如果目标是在$80000000时具有$7FFFFFFF的值，否则为零
  adds r0,r1,r1,asr #31 ; 只有在$80000000时才会溢出
  movvc r0,#0
; 如果事先已知进位被设置
  addcs r0,r1,r1 ; 只有在$80000000时才会溢出（值为1）
  movvc r0,#0
; 如果已知寄存器r2持有#1
  adds r0,r1,r1,asr #31
  ; 如果是$80000000，则MSB和进位设置
  sbc r0,r2,r0,lsr #31

这些都不是完美的解决方案，但它们很有意思。

- supercat