12

基本的な算術演算のみを使用して、XOR演算（2つの32ビット整数）をどのように実装できますか？2の累乗ごとに順番に除算した後、ビット単位で実行する必要がありますか、それともショートカットがありますか？実行速度は、最も単純で最短のコードほど重要ではありません。

編集： これは宿題ではありませんが、hacker.orgに提起されたなぞなぞです。重要なのは、操作が非常に制限されたスタックベースの仮想マシンにXORを実装することです（brainfuck言語に似ており、シフトやmodはありません）。そのVMを使用することは難しい部分ですが、もちろん、短くて単純なアルゴリズムによって簡単になります。

FryGuyのソリューションは巧妙ですが、その環境でも比較を使用するのは難しいため、元の理想（litbのソリューションと同様）を使用する必要があります。

4

4 に答える 4

17

私はそれを簡単な方法で行います：

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;

もっと簡単な方法があるかもしれませんが、私にはわかりません。

于 2008-12-17T02:04:36.020 に答える
10

これがあなたの質問の要点に反するかどうかはわかりませんが、次のように、AND、OR、および NOT を使用して XOR を実装できます。

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

英語では、それは「a or b, but not a and b」であり、XOR の定義に正確に対応しています。

もちろん、算術演算子のみを使用するというあなたの規定に厳密に固執しているわけではありませんが、少なくともこれは単純で理解しやすい再実装です。

于 2008-12-17T00:45:35.383 に答える
8

申し訳ありませんが、私は頭の中で単純なものしか知りません：

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 の代わりにコメント内の代替を使用できます。しかし、繰り返しになりますが、ソリューションも正確に高速ではなく、奇妙に見えます:)

于 2008-12-17T00:32:32.587 に答える
1

AND があると簡単です。

A OR B = A + B - (A AND B)

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

int customxor(int a, int b)
{
    return a + b - 2*(a & b);
}
于 2008-12-17T01:02:25.070 に答える