bit-manipulation - 根据 ADD、SUB、AND 实现 XOR 并在相等/不相等时分支？

Question

我有一个关于在 ADD/SUB 和分支方面实施 XOR 的面试问题：

仅使用以下命令实现两个数字之间的异或运算：

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

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

Answer 1

由于a + b可以扩展为(a ^ b) + ((a & b) << 1)，如果-+, -, &运算符可用，则以下成立：

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 进行异或