language-agnostic - 如何使用 +-*/ 实现 XOR？

Question

如何仅使用基本算术运算来实现 XOR 操作（在两个 32 位整数上）？依次除以2的每个幂后是否必须按位进行，还是有捷径？我并不关心执行速度，而是关心最简单、最短的代码。

编辑： 这不是家庭作业，而是在hacker.org上提出的一个谜语。关键是在基于堆栈的虚拟机上实现 XOR，操作非常有限（类似于Brainfuck语言，是的 - 没有 shift 或 mod）。使用该虚拟机是困难的部分，尽管通过一种简短而简单的算法当然会变得更容易。

虽然 FryGuy 的解决方案很聪明，但我将不得不采用我最初的理想（类似于 litb 的解决方案），因为在那种环境中也很难使用比较。

score 17 · Accepted Answer

我会用简单的方法来做：

uint xor(uint a, uint b):    

uint ret = 0;
uint fact = 0x80000000;
while (fact > 0)
{
    if ((a >= fact || b >= fact) && (a < fact || b < fact))
        ret += fact;

    if (a >= fact)
        a -= fact;
    if (b >= fact)
        b -= fact;

    fact /= 2;
}
return ret;

可能有更简单的方法，但我不知道。

score 10 · Accepted Answer

我不知道这是否违背了您的问题的要点，但是您可以使用 AND、OR 和 NOT 实现 XOR，如下所示：

uint xor(uint a, uint b) {
   return (a | b) & ~(a & b);
}

在英语中，那是“a or b, but not a and b”，它精确地映射到 XOR 的定义。

当然，我并没有严格遵守您只使用算术运算符的规定，但至少这是一个简单、易于理解的重新实现。

score 8 · Accepted Answer

对不起，我只知道直截了当的头脑：

uint32_t mod_op(uint32_t a, uint32_t b) {
    uint32_t int_div = a / b;
    return a - (b * int_div);
}

uint32_t xor_op(uint32_t a, uint32_t b) {
    uint32_t n = 1u;
    uint32_t result = 0u;
    while(a != 0 || b != 0) {
        // or just: result += n * mod_op(a - b, 2);
        if(mod_op(a, 2) != mod_op(b, 2)) {
            result += n;
        }
        a /= 2;
        b /= 2;
        n *= 2;
    }
    return result;
}

可以使用注释中的替代方法代替 if 以避免分支。但是话又说回来，解决方案也不是很快，而且看起来很奇怪:)

score 1 · Accepted Answer

如果你有 AND 会更容易，因为

A OR B = A + B - (A AND B)

A XOR B = A + B - 2(A AND B)

int customxor(int a, int b)
{
    return a + b - 2*(a & b);
}

language-agnostic - 如何使用 +-*/ 实现 XOR？

4 回答 4

Related

Reference