ちょっとはITの勉強するかと思い、XORのアルゴリズムについて頭をめぐらしています。
XORの基本
排他的論理和（XOR）とは「2つの値が異なる場合に1、同じ場合に0」になる論理演算です。
10進数でXORを求める場合も、CPU内部では2進数としてビットごとに演算されます。
例えば、ある数列のXORを求める場合、各要素をビット単位で順番にXORする必要があります。
これは、通信などで誤りを検出するパリティ計算の仕組みと同じ原理です。
数列の値がランダムである場合、ソフトウェアレベルのアルゴリズムだけでは全要素を確認する必要があるため、本質的な高速化はできません。
※等差数列とかの場合は算術の工夫で行けるようです。
大量データを高速に処理するには、NICやルータのような通信終端装置に組み込まれた専用ハードウェアで並列演算するのが一般的です。
※汎用CPUでも計算は可能ですが、並列化されていないため高速演算は難しいようです。
もっと賢いやり方…つまり、アルゴリズムで高速化できるのかな？と思いましたが、数列内のすべての値を見る必要があるため計算量は０（ｎ）よりも小さくならないみたいです。
数列内の値をXORするコード(PHP)
<?php
$n = fgets(STDIN);
$a = explode(' ', trim(fgets(STDIN)));
$r = 0;
for($i = 0; $i < $n; $i++){
$r ^= intval($a[$i]);
}
echo $r;
?>
【ポイント】
※$nは数列のアイテム数、$aは数列、$rは結果。
※XORや関数を使用すると論理演算XORで低速なので、^というビット単位のXOR演算子を使用している。
※paizaの場合はtrimやintvalせずとも動くが念の為（というかどんな環境でも）動くように入れている。
コメント