XOR交換アルゴリズム
過去ブログの転載です。
プログラミングで値の交換をするとき、ちょっと困ることがあります。例えば、変数Aと変数Bがあったとして、Aの値をBに、Bの値をAに、それぞれ交換することを考えます。しかしプログラムでは値のコピーはできても、値の交換を直接行うことができません。
A＝1234、B＝5678を交換しようとして、AにBの値をコピーしてしまうと
A＝5678、B＝5678となってしまい、もともとのAの値であった1234が消えてしまいます。
これでは交換できませんね。そのため普通は下の図のように、もう一つ変数を用意する必要があります。
一時変数tempにAの値をコピーすることで、Aの値を退避させておきます。それからBの値をAにコピーして、最後にtempの値をBにコピーします。これで交換ができます。
このように、変数の交換はちょっと手間なのです。
現実でもそうですよね。両手がふさがっているときは、一旦どちらかをどこかに置いて片手を空けてから交換を行います。それと同じことです。
ところが、整数のデータに限ってはこのtempがなくても交換できるXOR交換アルゴリズムというものを使うことができます。XORという演算を使えば、不思議なことが起こってAとBが交換されるのです。
XOR交換アルゴリズム
XOR（排他的論理和）とは、次のような2進数の演算です。
例えば、12 XOR 15 ＝ 3 になります。
それぞれ2進数に直すと、12は1100、15は1111、となり、これを筆算のように縦に並べます。これを足し算の筆算のように各桁足し算していくのですが、普通の足し算とは異なって1＋1＝0となるように計算します。
上の例では0＋1＝1となっていますが、1＋1＝0となるので、上の桁が落ちていって0011が答えとなります。0011は10進数に直すと3ですから、3が答えになります。
そして、このXORを使って、次のような計算を順番に行っていきます。
① A XOR B の値をAに代入
② A XOR B の値をBに代入
③ A XOR B の値をAに代入
A XOR B をひたすら計算しながら代入していくだけですね。A＝12, B＝15の例で実際にやってみます。
① 12 XOR 15 ＝ 3 をAに代入 … A＝3, B＝15
② 3 XOR 15 ＝ 12 をBに代入 … A＝3, B＝12
③ 3 XOR 12 ＝ 15 をAに代入 … A＝15, B＝12
なんと、AとBの値が入れ替わっていますね！
このように、XORを使うとtempを使わずに値の交換が出来てしまうのです。
回路図のイメージは上図のようになります。途中にある3つの素子がXOR演算を表していて、左の二入力に対するXORの結果が右に出ます。
上はA＝1234、B＝5678の例です。確かにAとBが交換されていますね。
交換の仕組み
XORを使うと何で値の交換が出来るのか確認してみます。XOR演算には、次のような性質があります。
① 結合法則が成り立つ … (A XOR B) XOR C ＝ A XOR (B XOR C)
② 交換法則が成り立つ … A XOR B ＝ B XOR A
③ 自分自身との演算結果が0（単位元）になる … A XOR A ＝ 0
これら3つの性質のおかげで、XOR交換アルゴリズムが実現します。手順ごとに格納される値を確認していきます。AとBの値がどんどん変わっていきますので、最初の値をそれぞれA1, B1とします。
① A1 XOR B1 ＝ A2とする
② A2 XOR B1 ＝ B2とする
③ A2 XOR B2 ＝ A3とする
B2＝A1, A3＝B1になって値が入れ替わっている、という手順でした。それぞれ求めていきます。
B2 ＝ A2 XOR B1 ＝ (A1 XOR B1) XOR B1
＝ A1 XOR (B1 XOR B1) … 結合法則
＝ A1 XOR 0 … 自分自身が逆元
＝ A1 … 0は単位元
A3 ＝ A2 XOR B2 ＝ (A1 XOR B1) XOR A1
＝ (B1 XOR A1) XOR A1 … 交換法則
＝ B1 XOR (A1 XOR A1) … 結合法則
＝ B1 XOR 0 … 自分自身が逆元
＝ B1 … 0は単位元
以上のように、確かに B2＝A1, A3＝B1 が成り立っています。これがXORを使って値交換が出来る仕組みです。逆に言えば、最初に挙げた3つの法則を持っている演算なら同様にして交換アルゴリズムに使えるのです。
他の演算を使った例
結合法則、交換法則が成り立ち、さらに自分自身と演算すると単位元になる、という3つの法則を持った演算なら、XORでなくてもこの交換アルゴリズムは使えます。
あんまりそういう演算の例がないのですが、例えばこんなものがあります。
√a×√b＝√(ab) を計算し、ルートの外に係数で出せるものを出して整理して、k√cとなるとき a ☆ b ＝ c と表す演算子☆
この演算子☆は、上記の3つの法則が成り立ちます。
ただし、a, b, cの素因数にもともと偶数乗の素因数が入ってしまっていると何もしなくてもルートの外に出てしまうので、そういう値には適用できません。実用性はないでしょう……単なる例です。
① A ☆ B の値をAに代入
② A ☆ B の値をBに代入
③ A ☆ B の値をAに代入
A＝1234, B＝5678 でやってみましょう。√1234も√5678も、これ以上ルートの中身が整理できないので、このアルゴリズムが適用できます。
① √1234×√5678＝2√1751663 より A＝1751663, B＝5678
② √1751663×√5678＝2839√1234 より A＝1751663, B＝1234
③ √1751663×√1234＝617√5678 より A＝5678, B＝1234
確かに入れ替わりましたね！
割と自分自身が逆元という性質を満たす演算を探すのが難しいですが、見つけることができればこのように交換アルゴリズムを考えることができます。
いろいろ探してみて、ぜひ遊んでみましょう＾＾！
余談ですが、XORのグラフは下図のようになります。
X座標、Y座標に対する点の明るさを X XOR Y の大きさにしています。（明るいほど大きな値）キレイなフラクタル図形になるのですね！ 2進数の演算をグラフにすると割と幾何学模様が現れて面白いです。
