Wie setzen Sie XOR + - * /?

Question

Wie kann die XOR-Verknüpfung (auf zwei 32-Bit-Ints) unter Verwendung von nur Operationen Grundrechen umgesetzt werden? Haben Sie es tun bitweise nach durch jede Potenz von 2 wiederum teilt, oder gibt es eine Abkürzung? Ich kümmere mich nicht so viel über die Ausführungsgeschwindigkeit, wie etwa die einfachste, kürzeste Code.

Edit: Dies ist nicht Hausaufgaben, aber ein Rätsel stellte auf einem hacker.org . Der Punkt ist, mit sehr begrenzten Operationen (ähnlich das Gehirnfick Sprache und ja - keine Verschiebung oder mod). Mit der VM ist der schwierigste Teil, wenn auch natürlich durch einen Algorithmus erleichtert, die kurz und einfach ist.

Während FryGuy Lösung clever ist, werde ich mit meiner ursprünglichen ideal gehen (ähnlich der Lösung litb), weil Vergleiche schwierig sind in dieser Umgebung als auch zu verwenden.

Answer 1

Es tut mir leid, ich weiß nur die gerade nach vorne eine 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 dem verwendet werden, wenn Verzweigung zu vermeiden. Aber dann wieder, ist die Lösung nicht genau schnell entweder und es macht es fremd aussehen :)

Answer 2

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 ein einfacher Weg sein, aber ich weiß nicht, von einem.

Answer 3

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

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

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

Natürlich ich bleibe nicht streng auf Ihre Bestimmung nur die arithmetischen Operatoren verwenden, aber zumindest dieses eine einfache, leicht zu versteh Neuimplementierung.

Answer 4

Es ist einfacher, wenn Sie das und weil

haben

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