Help us understand the problem. What is going on with this article?

XOR交換アルゴリズムって面白い

More than 3 years have passed since last update.

はじめに

サンプルコードは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
Riliumph
しがないC++/Pythonが大好きなエンジニア。 Java(Servlet/JSP), HTML5, C/C++(with Boost), Python3, C#とか色々仕事してきました。 今は組み込みC言語やってます。 もっと羽振りのいい会社に行きたいよね(´・_・`)ハァー
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした