Как реализовать XOR с помощью + - * /?
Как можно реализовать операцию XOR (на двух 32-битных int), используя только базовые арифметические операции? Придется ли вам делать это поразрядно после деления на каждую степень двойки по очереди, или есть ярлык? Меня не столько заботит скорость выполнения, сколько самый простой и короткий код.
Редактировать: Это не домашнее задание, а загадка на hacker.org. Дело в том, чтобы реализовать XOR на виртуальной машине на основе стека с очень ограниченными операциями (аналогично языку ебать мозги и да - без сдвига или мода). Использование этой виртуальной машины - сложная часть, хотя, конечно, упрощается благодаря короткому и простому алгоритму.
Хотя решение FryGuy является умным, мне придется придерживаться своего первоначального идеала (похожего на решение litb), потому что сравнения также трудно использовать в этой среде.
x << a === x * (1 << a) x >> a === x / (1 << a)
Похоже на домашнее задание. Я всегда считал лучшей практикой цитировать любые внешние ссылки, но было бы довольно нагло цитировать свой собственный вопрос о stackoverflow. Какая этическая дилемма.
Ответы 4
Извините, я знаю только одно прямое в голове:
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, чтобы избежать ветвления. Но опять же, решение тоже не совсем быстрое, и оно выглядит страннее :)
вы должны вернуть бит результата в конце.
Я тестировал его на codepad.org и работает :) Мне пришлось бы вернуться, если бы я сделал результат * = 2; но вместо этого я использую n, чтобы добавить 1 бит к результату. так что мне не нужно возвращаться в конце
да, я тоже его тестировал и он работает нормально, мой плохой =)
Я пришел к такому же решению. +1
Другой способ - проверить "mod_op (a - b, 2)! = 0", но это зависит от поведения "недополнения" языка программирования, поэтому лучше не вставлять его :)
Я не знаю, нарушает ли это суть вашего вопроса, но вы можете реализовать XOR с помощью AND, OR и NOT, например:
uint xor(uint a, uint b) {
return (a | b) & ~(a & b);
}
На английском это «a или b, но не a и b», что точно соответствует определению XOR.
Конечно, я не придерживаюсь строго вашего условия использования только арифметических операторов, но, по крайней мере, это простая и легкая для понимания повторная реализация.
Проголосовали против, да? Дважды? Хотя мой ответ относится к несколько иному сценарию, чем тот, который определен OP, я думаю, что он по-прежнему предоставляет полезную вспомогательную информацию.
Я собирался задать вопрос, на который это дает ответ - так что, по крайней мере, вы получите от меня положительный голос. знак равно
Это проще, если у вас есть И, потому что
А ИЛИ В = А + В - (А И В)
А ИСКЛЮЧАЮЩЕЕ ИЛИ B = A + B - 2 (А И В)
int customxor(int a, int b)
{
return a + b - 2*(a & b);
}
Я бы сделал это просто:
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;
Может быть более простой способ, но я не знаю ни одного.
Голосование, кажется, самая простая реализация.
мне это тоже нравится. руки вниз, как бы я ни любил свой прямой путь, но вы заслуживаете голосования :)
вы не возражаете против сдвига и оператора модуля?