代码之家 › 专栏 › 技术社区 › Michael Borgwardt

如何使用+-*/实现XOR?

xor bit-manipulation language-agnostic

12

Michael Borgwardt · 技术社区 · 16 年前

如何仅使用基本算术运算来实现XOR运算(在两个32位整数上)?你必须依次除以2的每一个幂次,还是有捷径?我不在乎执行速度,只关心最简单、最短的代码。

编辑: 这不是家庭作业,而是在 hacker.org . 重点是在操作非常有限的基于堆栈的虚拟机上实现XOR(类似于 brainfuck 语言和是-不转换或修改)。使用虚拟机是一个困难的部分,当然,通过一个简短而简单的算法变得更容易。

虽然fryguy的解决方案很聪明,但我还是要遵循我最初的理想(类似于litb的解决方案),因为在那种环境中,比较也很难使用。

4 回复 | 直到 12 年前

1

8

Johannes Schaub - litb 16 年前

对不起,我只知道直发的那个:

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。但同样的,解决方案也不是很快,这让它看起来很奇怪:)

2

17

FryGuy 16 年前

我会用简单的方法:

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;

也许有一个更简单的方法,但我不知道。

3

11

benjismith 16 年前

我不知道这是否会破坏您的问题,但是您可以用and,or,and,not来实现XOR,如下所示:

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

在英语中,这是“a或b,但不是a和b”,它精确地映射到xor的定义。

当然,我并不是严格按照你的规定只用算术运算符,但至少这是一个简单易懂的再实现。

4

1

Community CDub 12 年前

如果你有并且因为

A或B=A+B-(A和B)

a xor b=a+b-2(a和b)

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