IT｜排他的論理和とは？ある数列の排他的論理和を求めるには？

ちょっとはITの勉強するかと思い、XORのアルゴリズムについて頭をめぐらしています。

XORの基本
数列内の値をXORするコード(PHP)

XORの基本

排他的論理和（XOR）とは「2つの値が異なる場合に1、同じ場合に0」になる論理演算です。

10進数でXORを求める場合も、CPU内部では2進数としてビットごとに演算されます。

例えば、ある数列のXORを求める場合、各要素をビット単位で順番にXORする必要があります。

これは、通信などで誤りを検出するパリティ計算の仕組みと同じ原理です。

数列の値がランダムである場合、ソフトウェアレベルのアルゴリズムだけでは全要素を確認する必要があるため、本質的な高速化はできません。

したがって大量データを高速に処理するには、NICやルータのような通信終端装置に組み込まれた専用ハードウェアで並列演算するのが一般的です。

もっと賢いやり方…つまり、アルゴリズムで高速化できるのかな？と思いましたが、数列内のすべての値を見る必要があるため結局のところ計算量は０（ｎ）よりも小さくならないみたいです。あまり汎用CPUで大量データを高速にXORしたいというシーンはあまりない気がしますが、そういう事情があることを知っておくとどこかで役立つかもしれません。

※なお等差数列とかの場合は、算術の工夫で高速化できるようです。

※汎用CPUでも計算は可能ですが、並列化されていないため高速演算は難しいようです。

数列内の値をXORするコード(PHP)


&lt;?php
    $n = fgets(STDIN);
    $a = explode(' ', trim(fgets(STDIN)));
    $r = 0;
    for($i = 0; $i &lt; $n; $i++){
        $r ^= intval($a[$i]);
    }
    echo $r;
?&gt;

【ポイント】

※$nは数列のアイテム数、$aは数列、$rは結果です。

※XORやvariant_xor関数を使用する論理演算XORで低速なので、^というビット単位のXOR演算子を使用しています。

※paizaの場合はtrimやintvalせずとも動くが念の為（というかどんな環境でも）動くように入れています。