在ADD,SUB,AND方面实现XOR并在相等/不相等的分支上实现？

Question

我有一个关于在ADD/SUB和分支方面实现XOR的面试问题:在两个数字之间实现Xor操作仅使用以下命令:

1. 加
2. 子
3. 分支如果相等
4. 分支如果不相等
5. 和

您可以使用寄存器r3和r4作为额外空间.假设寄存器r1存储第一个数字,r2存储第二个数字

Answer 1

由于a + b可以扩展为(a ^ b) + ((a & b) << 1),如果+, -, &-operators可用,则以下内容成立:

a ^ b == a + b - (a & b) - (a & b).

实际上,gcc 8.2.1优化了以下c函数

unsigned foo(unsigned a, unsigned b)
{
   return a + b - (a & b) - (a & b);
}

到以下x86-64程序集-O3:

foo:
    movl    %edi, %eax
    xorl    %esi, %eax
    ret

因此,既不需要分支指令,也不需要三个寄存器(以下是伪装配):

$r1 = a          //first argument
$r2 = b          //second argument
$r3 = $r1 & $r2  //one temp register is enough
$r1 = $r1 + $r2
$r1 = $r1 - $r3
$r1 = $r1 - $r3  //$r1 is the return value

Answer 2

使用 SUB，您可以获得 NOT

~a = ~0 - a

或者如果使用了二进制补码

~a = -a - 1

从 AND 和 NOT 你得到功能完整的NAND ，因此你可以轻松地执行任何逻辑功能。有多种方法可以从中获取 XOR。其中之一是

t = a NAND b
a ^ b = (a NAND t) NAND (b NAND t)

或者

a ^ b = (b NAND ~a) NAND (a NAND ~b)

可以翻译成这样的

r3 = ~0 - r1  # ~a
r4 = r2 & r3  # b & ~a
r4 = ~r4      # b NAND ~a
r2 = ~0 - r2  # ~b
r2 = r2 & r1  # a & ~b
r2 = ~r2      # a NAND ~b
r1 = r2 & r4
r1 = ~r1      # a ^ b

但它不会像直接利用加法器的属性那样有效

您可以从互斥或等价中找到许多其他方法

a ^ b = (a | b) & ~(a & b) = ~(~a & ~b) & ~(a & b)
a ^ b = ~(a & b) & (a | b) = ~(a & b) & ~(~a & ~b)

请参阅XOR 是 AND 和 NOT 运算符的组合吗？

相关：仅来自 OR 和 AND 的 XOR