Javaでサイズ4のグループごとの要素の異なるXORを使って配列を求める方法

問題の概要

サイズN(4の倍数)の整数型配列が与えられ、この配列に対して排他的論理和(XOR)演算を行います。入力配列 input[1〜4] が utility_arr[1〜4] に対応するように変換するのが目的です。計算の条件は次のとおりです。

arr[1〜4] = {a1, a2, a3, a4} のとき、
q[1〜4] = {a1 ⊕ a2 ⊕ a3, a1 ⊕ a2 ⊕ a4, a1 ⊕ a3 ⊕ a4, a2 ⊕ a3 ⊕ a4}

つまり、各グループの4つの要素から3つずつを選んでXORを計算し、その結果を除外した要素の位置に格納していきます。

入出力シナリオ

例1

入力: int[] input = { 5, 2, 3, 4 };

出力: XOR演算後の結果: 4 3 2 5

説明: 排他的論理和(XOR)ゲートは、2つの入力端子の論理レベルが互いに「異なる」場合にのみ出力が「HIGH(1)」になります。2つの入力AとBがどちらも論理レベル「1」または「0」であれば出力は「0」となり、このためXORゲートは「奇数パリティゲート」とも呼ばれます。言い換えると、入力に含まれる1の個数が奇数のときに出力が「1」になるという性質を持っています。

• a1 ⊕ a2 ⊕ a3 = 5 ⊕ 2 ⊕ 3 = 4
• a1 ⊕ a2 ⊕ a4 = 5 ⊕ 2 ⊕ 4 = 3
• a1 ⊕ a3 ⊕ a4 = 5 ⊕ 3 ⊕ 4 = 2
• a2 ⊕ a3 ⊕ a4 = 2 ⊕ 3 ⊕ 4 = 5

例2

入力: int[] input = { 7, 6, 4, 4, 3, 8, 9, 5 };

出力: XOR演算後の結果: 5 5 7 6 2 14 15 4

説明: この処理は、サイズが4の倍数である入力配列に対してのみ正しく機能します。それ以外のサイズの配列では、奇数番目の位置に0が表示されるので注意が必要です。

プログラムで使用しているアプローチ

このプログラムでは、XORの基本的な性質を活用しています。

• XORの性質: a ⊕ a = 0、a ⊕ 0 = a が成り立ちます。また、(a ⊕ b ⊕ c) ⊕ (b ⊕ c ⊕ d) = a ⊕ d となります((b ⊕ c) ⊕ (b ⊕ c) = 0 となるため)。

• 計算のために、配列を4要素ずつのグループに分割し、XORの性質に従って各グループの結果を求めます。

• 上記の性質を応用すると、(a ⊕ d) を使って b と c を計算できます。
  (a ⊕ b ⊕ d) ⊕ (a ⊕ d) = b
  (a ⊕ c ⊕ d) ⊕ (a ⊕ d) = c

• さらに、求めた b と c を使えば、a と d も次の方法で導き出せます。
  (a ⊕ b ⊕ c) ⊕ (b) ⊕ (c) = a
  (b ⊕ c ⊕ d) ⊕ (b) ⊕ (c) = d

• この一連の処理を、すべての4要素グループに対して繰り返し適用します。

• 2つのポインタ i と j を使ったループを、配列の長さを4で割った回数だけ実行します。あわせて、一時的な値を保持する変数 ans と、計算結果を格納するユーティリティ配列を用意します。

• forループ内では、次のXOR演算を実行します。

  ans = 入力配列[i] ⊕ 入力配列[i+3]
  ユーティリティ配列[i+1](bの計算)= 入力配列[i+1] ⊕ ans
  ユーティリティ配列[i+2](cの計算)= 入力配列[i+2] ⊕ ans
  ユーティリティ配列[i](aの計算)= 入力配列[i] ⊕ ((ユーティリティ配列[i+1]) ^ (ユーティリティ配列[i+2]))
  ユーティリティ配列[i+3](dの計算)= 入力配列[i+3] ⊕ ((ユーティリティ配列[i+1]) ^ (ユーティリティ配列[i+2]))

• その後、ポインタを更新して次の4要素のセットへ処理を進めます。

• 最後に、配列全体を出力し、結果をユーザーに返します。

なお、このアルゴリズムの計算量はO(N)です。配列を一度走査するだけで全グループの変換が完了するため、非常に効率的な手法といえます。

コード例

import java.util.Arrays;
import java.util.List;

public class Tutorials {
    static int ans = 0;
    public static void main(String args[]){
        int[] input = {7, 1, 2, 3};
        int[] arr = new int[input.length];
        for (int i = 0, j = 0; j < input.length / 4; j++){
            ans = input[i] ^ input[i + 3];
            arr[i + 1] = input[i + 1] ^ ans;
            arr[i + 2] = input[i + 2] ^ ans;
            arr[i] = input[i] ^ ((arr[i + 1]) ^ (arr[i + 2]));
            arr[i + 3] = input[i + 3] ^ (arr[i + 1] ^ arr[i + 2]);
            i += 4;
        }
        System.out.println("サイズ4のグループごとの要素の異なるXORの結果: ");
        for (int i = 0; i < arr.length; i++){
            System.out.println(arr[i]);
        }
    }
}

出力

上記のコードを実行すると、次の出力が得られます。

サイズ4のグループごとの要素の異なるXORの結果 :
4
5
6
0