Как реализовать XOR с помощью + - */?

Как можно выполнить операцию XOR (по двум 32-битным ints) с использованием только основных арифметических операций? Вам нужно сделать это поразрядным после деления на каждую мощность 2 по очереди или есть ярлык? Я не забочусь о скорости выполнения так же, как о простейшем, кратчайшем коде.

Edit: Это не домашнее задание, а загадка, созданная на hacker.org. Дело в том, чтобы реализовать XOR на виртуальной машине на основе стека с очень ограниченными операциями (аналогично brainfuck и да - без сдвига или мод). Использование этой виртуальной машины - трудная часть, хотя, конечно, она упрощается по короткому и простому алгоритму.

В то время как решение FryGuy является умным, мне придется пойти с моим оригинальным идеалом (аналогичным решению с подсветкой), потому что сравнения трудно использовать в этой среде.

Ответ 1

Мне жаль, что я знаю только один вперед:

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

Я бы сделал это простым способом:

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

Я не знаю, побеждает ли это вопрос вашего вопроса, но вы можете реализовать XOR с помощью AND, OR и NOT, например:

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

По-английски это "a или b, но не a и b", которое точно соответствует определению XOR.

Конечно, я не придерживаюсь строгого положения о том, чтобы использовать только арифметические операторы, но, по крайней мере, это простая, легко понятная повторная реализация.

Ответ 4

Это проще, если у вас есть 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);
}