はじめに
サンプルコードはwandobox様で一応動作確認していますが誤っていたらすいません。
数学科とか出てないので間違ってたらすいません。
XOR演算
2値が一致しているか2値が相違しているかどうかで結果が変わる演算です。
特に難しいことはないと思いますが、同期の丸暗記おじさんに教えたら「なるほどー」と言われました。
もし、丸暗記が辛かったらこんな風に法則で覚えると良いですよ
※XOR演算がそういう目的のモノなのかは知らないので覚え方だけですよ！
| A | B | 演算結果 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
交換アルゴリズム
2値の交換って普通に考えると下記のようなコードになると思います。
wandbox_sample
print('---------- RAW DATA ----------')
obj1 = 10
obj2 = 20
print("obj1: ", obj1)
print("obj2: ", obj2)
print('---------- SWAPED DATA ----------')
tmp_obj = obj1
obj1 = obj2
obj2 = tmp_obj
print("obj1: ", obj1)
print("obj2: ", obj2)
これってtmp_objなんて一時変数をわざわざ用意する必要があります。
別に用意してもいいんですけど、
- 一時変数って何の役割の変数か後で見たときに分からない
- メモリがキツキツの環境だとそういうのも削減したい
とかある訳ですよ。知らないけど。
そんな悩みを解決できる奴がいたんです。
その名も……
XOR交換アルゴリズム
wandbox_sample
print('---------- RAW DATA ----------')
obj1 = 7
obj2 = 12
print("obj1: ", obj1)
print("obj2: ", obj2)
print('---------- SWAPED DATA ----------')
obj1 = obj1 ^ obj2
obj2 = obj1 ^ obj2
obj1 = obj1 ^ obj2
print("obj1: ", obj1)
print("obj2: ", obj2)
ホントに一時変数がなくなった……
確かめてみる
コードの概要はこれでした。
wandbox_sample
A = 7
B = 12
A = A ^ B
B = A ^ B
A = A ^ B
\begin{align}
A = 0111\\
B = 1100\\
A &= A \ xor \ B \\
&=0111 \ xor \ 1100\\
&=1011\\
B &= A \ xor \ B \\
&= 1011 \ xor \ 1100\\
&= 0111\\
A &= A \ xor \ B\\
&= 1011 \ xor \ 0111\\
&= 1100\\
A = 1100\\
B = 0111
\end{align}
確かに入れ替わった！！
XORの法則
前提として下の法則があります。
1. 交換法則
xor演算子の左辺・右辺は交換ができる。
A \ xor \ B = B \ xor \ A\\
具体例
A = 0111とする\\
B = 1100とする\\
A \ xor \ B = 1011\\
B \ xor \ A = 1011
2. 結合法則
計算の優先を変化させても結果は変わらない。
(A \ xor \ B) \ xor \ C = A \ xor \ (B \ xor \ C)
具体例
A=0111とする\\
B=1100とする\\
C=1001とする\\
\begin{align}
(A \ xor \ B) \ xor \ C &= 1011 \ xor \ 1001\\
&= 0010\\
A \ xor \ (B \ xor \ C) &= 0111 \ xor \ 0101\\
&= 0010\\
\end{align}
3. 単位元
Z=0という値があり任意のAとxorするとAが求まる。
計算しても変化しない奴もいますよってこと
具体例
A = 0111とする\\
Z = 0000とする\\
A \ xor \ Z = 0111 (=A)
4. 逆元（インバース？）
任意のAとxorすると0になる値A^-1を持つ。
なんか逆行列みたいな関係のやつ
A = 0111とする\\
A \ xor \ A^{-1} = 0と仮定すると、\\
\begin{align}
A^{-1} &= 0111\\
&= A
\end{align}
あれ？自身が逆元だ。おもしろい。
証明？
\begin{align}
A &= A \ xor \ B\\
B &= A \ xor \ B\\
&= (A \ xor \ B) \ xor \ B（結合法則で変形すると…）\\
&= A \ xor \ (B \ xor \ B)（逆元の存在で計算すると…）\\
&= A \ xor \ 0（単位元の存在で計算すると…）\\
&= A（入れ替わったー！）\\
A &= A \ xor \ B\\
&= (A \ xor \ B) \ xor \ A（交換法則で変形すると…）\\
&= (B \ xor \ A) \ xor \ A（結合法則で変形すると…）\\
&= B \ xor \ (A \ xor \ A)（逆元の存在で計算すると…）\\
&= B \ xor \ 0（単位元の存在で計算すると…）\\
&= B（入れ替わったー！）\\
\end{align}
なるほどー(´･_･`) （計算式上成り立つのは分かったけど、ピンと来てない顔
これはスゴイな！！
追記
これはアルゴリズムのお話なんで、こんなの書きましたけど、
実際に書くときは標準ライブラリに入ってるであろうswap関数を使った方がいいですよ
特にC/C++辺りの独自実装は危険な香りしかしないので、標準ライブラリ頼みな自分です。
Pythonはswap関数がないので、こういう書き方をしますね。
wandbox_sample
obj1 = 10
obj2 = 20
obj1, obj2 = obj2, obj1