【JavaScript】配列内の奇数回出現する整数をXOR演算で見つける方法

整数の配列が与えられ、「ある1つの要素を除いて、すべての要素が偶数回出現する」という条件が課せられます。私たちの課題は、その例外となる要素をたった1回の反復処理で見つけ出すことです。

ここでは、次のサンプル配列を使って考えてみましょう。

[1, 4, 3, 4, 2, 3, 2, 7, 8, 8, 9, 7, 9]

この配列では、1だけが1回（奇数回）出現し、それ以外の4、3、2、7、8、9はすべて2回（偶数回）出現しています。人間の目で見れば答えはすぐ分かりますが、プログラムで効率よく求めるにはどうすればよいのでしょうか。

XOR（排他的論理和）演算子の基礎知識

この問題を解く鍵となるのが、ビット演算子であるXOR（^）です。まずはその動作を理解しておきましょう。

XOR演算子は、2つのオペランドが互いに異なる値の場合にTRUE（1）を返し、同じ値の場合にはFALSE（0）を返します。

XOR演算子の真理値表

0 ^ 0 → 0
0 ^ 1 → 1
1 ^ 0 → 1
1 ^ 1 → 0

この動作を注意深く観察すると、重要な性質に気づきます。まったく同じ値同士のXOR演算（例：12 ^ 12）は常にFALSE、つまり0を返すのです。言い換えると、「偶数回出現した値はXORによって打ち消される」ということになります。そして、これこそまさに私たちが求めている性質です。

reduceメソッドを使った実装

この性質を応用すると、Array.prototype.reduce()メソッドを使って非常に簡潔にコードを書くことができます。

コード例

const sampleArray = [1, 4, 3, 4, 2, 3, 2, 7, 8, 8, 9, 7, 9];
console.log(sampleArray.reduce((a, b) => a ^ b));

仕組みの解説

このコードは配列の各要素を順番に走査しながら、累積的にXOR演算を適用していきます。XORには結合法則と交換法則が成り立つため、要素の出現順序に関係なく、偶数回出現する要素は互いに打ち消し合って0になり、最終的に残るのは奇数回出現する唯一の要素だけです。

このアプローチの優れた点は、計算コストの低さにあります。

• 時間計算量：O(n) — 配列を1回走査するだけで完了
• 空間計算量：O(1) — 追加の記憶領域がほぼ不要

ハッシュマップやSetを使って各要素の出現回数をカウントする方法もありますが、それらは追加のメモリを消費します。XORを使う手法は、余分なデータ構造なしに1回の反復で解決できる点が大きな魅力です。

実行結果

上記のコードを実行すると、コンソールには以下のように出力されます。

1

見事に、奇数回出現する要素「1」だけが取り出されました。このテクニックはコーディング面接でも頻出の定番問題なので、XORの性質と合わせてぜひマスターしておきましょう。