Pythonでビット単位のANDを使ってすべてのペアのXOR合計を効率的に求めるプログラム

問題の概要

2つの配列 arr1 と arr2 が与えられているとします。ここで「リストのXOR合計」とは、リスト内の全要素をビット単位XOR（排他的論理和）で結合した値のことを指します。リストに要素が1つしかない場合、そのXOR合計はその要素自体になります。

次に、0 <= i < len(arr1) および 0 <= j < len(arr2) を満たすすべてのインデックスペア (i, j) について、arr1[i] AND arr2[j]（ビット単位AND）の結果を要素として持つリストを考えます。この記事では、そのリスト全体のXOR合計を求める方法を解説します。

具体例

たとえば、入力が arr1 = [5, 3, 4]、arr2 = [2, 6] の場合を考えてみましょう。

まず、すべてのペアのANDを計算すると、次のリストが得られます。

[5 AND 2, 5 AND 6, 3 AND 2, 3 AND 6, 4 AND 2, 4 AND 6]
= [0, 4, 2, 2, 0, 4]

このリストのXOR合計は以下のようになります。

0 XOR 4 XOR 2 XOR 2 XOR 0 XOR 4 = 0

したがって、出力は 0 となります。

解法のアプローチ

すべてのペアを二重ループで総当たり的に計算することも可能ですが、より効率的な方法があります。手順は以下の通りです。

• xor1 := 0、xor2 := 0 と初期化します。
• arr1 の各要素 a に対して、xor1 := xor1 XOR a を実行します。
• arr2 の各要素 a に対して、xor2 := xor2 XOR a を実行します。
• 最後に xor1 AND xor2 を返します。

なぜこの方法で正しく求まるのか

ポイントは、AND演算がXORに対して分配法則を満たすという性質です。つまり、任意の整数 x, y, z について次の等式が成り立ちます。

(x XOR y) AND z = (x AND z) XOR (y AND z)

この性質を繰り返し適用すると、「すべてのペア (arr1[i] AND arr2[j]) のXOR」は「arr1 の全要素のXOR」と「arr2 の全要素のXOR」のANDに等しいことが分かります。そのため、O(n×m) の二重ループを回す代わりに、O(n + m) の計算量で答えを求めることができ、配列が大きい場合でも高速に処理できます。

Pythonでの実装例

それでは、上記のアルゴリズムをPythonで実装してみましょう。

def solve(arr1, arr2):
   xor1 = 0
   xor2 = 0
   for a in arr1:
      xor1 ^= a
   for a in arr2:
      xor2 ^= a
   return xor1 & xor2

arr1 = [5, 3, 4]
arr2 = [2, 6]
print(solve(arr1, arr2))

入力

[5, 3, 4], [2, 6]

出力

0

まとめ

この問題は、AND演算の分配法則を活用することで、各ペアを個別に計算せずに済むのが大きな特徴です。各配列のXOR合計を先に求めてからANDを取るだけでよいため、計算量は O(n + m) に抑えられます。ビット演算の数学的な性質を理解していれば、シンプルで効率的なコードが書ける好例といえるでしょう。