Jak zaimplementować XOR za pomocą + - * /?

Question

W jaki sposób można przeprowadzić operację XOR (na dwóch 32-bitowych liczbach zmiennych) przy użyciu tylko podstawowych działań arytmetycznych? Czy musisz zrobić to bitowo po podzieleniu przez każdą potęgę 2 po kolei, czy jest skrót? Nie dbam o szybkość wykonania tak bardzo, jak o najprostszy, najkrótszy kod.

Edit: To nie jest praca, ale zagadka stwarzane na hacker.org. Chodzi o implementację XOR na wirtualnej maszynie opartej na stosie z bardzo ograniczonymi operacjami (podobnie jak w przypadku języka brainfuck i tak - bez zmiany lub mod). Używanie tej maszyny wirtualnej jest trudną częścią, choć oczywiście łatwiejszą do wykonania przez algorytm, który jest krótki i prosty.

Podczas gdy rozwiązanie FryGuy jest sprytne, będę musiał przejść z moim oryginalnym ideałem (podobnym do rozwiązania litb), ponieważ porównywanie jest również trudne w tym środowisku.

Answer 1

Przepraszam wiem tylko prosto do przodu jeden w głowę:

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

Alternatywą w komentarzach mogą być stosowane zamiast chcąc uniknąć rozgałęzienia. Ale z drugiej strony rozwiązanie nie jest zbyt szybkie i sprawia, że ​​wygląda dziwniej :)

Answer 2

Nie wiem, czy to jest sprzeczne z celem pytania, ale można wdrożyć XOR z AND, OR, i NOT coś takiego:

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

w języku angielskim, to "a lub b, ale nie a i b", który odwzorowuje dokładnie definicji XOR.

Oczywiście, nie trzymam się ściśle warunku użycia wyłącznie operatorów arytmetycznych, ale przynajmniej to proste, łatwe do zrozumienia reimplementation.

Answer 3

Łatwiej jeśli masz a ponieważ

A lub B = A + B - (A i B)

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

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

Answer 4

chciałbym zrobić to w prosty sposó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; 

nie może być łatwiejszy sposób, ale nie wiem jednego.