Как вы реализуете XOR, используя + - * /?

Question

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

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

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

Answer 1

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

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;

Возможно, есть более простой способ, но я не знаю ни одного.

Answer 2

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

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

В английском языке это "a или b, но не a и b", что точно соответствует определению XOR.

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

Answer 3

Извините, я знаю только одно прямо в голове:

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, чтобы избежать ветвления. Но опять же, решение тоже не совсем быстрое и выглядит странно :)

Answer 4

Проще, если у вас есть AND, потому что

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);
}