Wie implementieren Sie XOR mit + - * /?

Question

Wie kann die XOR-Operation (auf zwei 32-Bit-Ints) nur mit arithmetischen Grundoperationen implementiert werden? Musst du es bitweise machen, nachdem du jede Potenz von 2 geteilt hast, oder gibt es eine Abkürzung? Die Ausführungsgeschwindigkeit ist mir weniger wichtig als der einfachste und kürzeste Code.

Edit: Dies ist keine Hausaufgaben, aber ein Rätsel stellte auf einem hacker.org. Der Punkt ist, XOR auf einer stack-basierten virtuellen Maschine mit sehr begrenzten Operationen zu implementieren (ähnlich der brainfuck Sprache und ja - keine Verschiebung oder Mod). Die Verwendung dieser VM ist der schwierige Teil, der natürlich durch einen Algorithmus, der kurz und einfach ist, vereinfacht wird.

Während die Lösung von FryGuy clever ist, muss ich mit meinem ursprünglichen Ideal (ähnlich der Lösung von litb) gehen, da Vergleiche in dieser Umgebung schwierig zu verwenden sind.

Answer 1

Es tut mir leid, ich weiß nur die gerade nach vorne ein in den Kopf:

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

Die Alternative in den Kommentaren kann statt der verwendet werden, wenn Verzweigung zu vermeiden. Aber dann ist die Lösung auch nicht genau so schnell und es macht es merkwürdiger :)

Answer 2

Ich weiß nicht, ob das den Punkt Ihrer Frage besiegt, aber Sie können XOR mit AND, OR und NOT implementieren , wie folgt aus:

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

in Englisch, ist das "a oder b, aber nicht a und b", die genau auf die Definition von XOR abbildet.

Natürlich halte ich mich nicht streng an Ihre Vorgabe, nur die arithmetischen Operatoren zu verwenden, aber zumindest ist dies eine einfache, leicht verständliche Neuimplementierung.

Answer 3

Es ist einfacher, wenn Sie die haben, und weil

A oder B = A + B - (A und B)

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

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

Answer 4

ich würde es die einfache Art und Weise tun:

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; 

es könnte einen einfacheren Weg sein, aber ich weiß nicht, von einem.