12

よくあるプログラミング インタビューの問題に出くわしました。符号なし整数のリストが与えられたとき、リスト内で奇数回出現する 1 つの整数を見つけます。たとえば、次のリストが与えられた場合:

{2,3,5,2,5,5,3}

他の整数は偶数回発生するのに対し、リスト内で 3 回発生するため、解は整数 5 になります。

私の最初の解決策は、並べ替えられた配列を設定し、配列を反復処理することでした。奇数要素ごとに整数を加算し、偶数要素ごとに減算します。他の整数が相殺されるため、最終合計が解決策でした。

しかし、各要素に対して XOR を実行するだけで、より効率的な解決策が存在することがわかりました。並べ替えられた配列は必要ありません。つまり、次のようになります。

2^3^5^2^5^5^3 = 5

私が取った Discrete Structures クラスから、Associate Property が XOR 操作に適用できることを思い出しました。それが、このソリューションが機能する理由です。

a^a = 0

と：

a^a^a = a

連想プロパティが XOR で機能することは覚えていますが、XOR に固有のこのプロパティの論理的証明を見つけるのに苦労しています (インターネット上のほとんどの論理的証明は、AND 操作と OR 操作に重点を置いているようです)。連想プロパティが XOR 操作に適用される理由を知っている人はいますか?

AND および/または OR を含む XOR ID が含まれていると思われます。

4

2 に答える 2

9

結合法則はそれを言い(a^b)^c = a^(b^c)ます。XORはビット単位であるため（数値のビットは並列に扱われます）、単一ビットのXORを考慮する必要があります。次に、すべての可能性を調べることで証明を行うことができます。

abc (a^b) (a^b)^c (b^c) a^(b^c)
000   0      0      0      0
001   0      1      1      1
010   1      1      1      1
011   1      0      0      0
100   1      1      0      1
101   1      0      1      0
110   0      0      1      0
111   0      1      0      1

3番目の列、(a^b)^cは5番目の列、と同じであるためa^(b^c)、結合法則が成り立ちます。

于 2012-11-07T14:11:04.033 に答える
1

である限りa ^ b == ~a & b | a & ~b、次のことを証明できます。

(a ^ b) ^ c = ~((~a & b) | (a & ~b)) & c | ((~a & b) | (a & ~b)) & ~c

と

a ^ (b ^ c) = a & ~((~b & c) | (b & ~c)) | ~a & ((~b & c) | (b & ~c))

等しいです。

于 2012-11-07T14:36:50.097 に答える