変数を入れ替えるときに、
x^=y; y^=x; x^=y;
(x^=yは、 x=x^y つまり x=x XOR y という意味です。) で入れ替えれることを知ったのですが、なぜそうなるのか分からなかったので実証してみました。
注意：xとyが同じ場合は0になるので、このアルゴリズムは完璧ではありあません
排他的論理和
まずはじめに、排他的論理和(XOR)についてざっくりと説明しておきます。 排他的論理和は、aかbが真でもう片方が偽のとき真となる演算です。つまり、両方が同じ真偽値でない時に真を返します。
論理式で表すと次の画像のようになります。
排他的論理和を2回繰り返すと下の画像のようになります。今回のメインはこの式の解析です。
展開
ではこれを計算していきます。計算量が多いので前のカッコと後ろのカッコを順番に展開していきます。まず前のカッコを展開します。
すっきりとしました。さて、後ろのカッコは先ほどよりも計算量が多いです。ですから、わかりやすいようにステップを細かく刻みました。一つ一つの工程はド・モルガンの法則、分配法則、その他基本的な法則が分かれば理解できると思います。
では、2つのかっこをあわせます。
これで、a=aとなり、元に戻りました。
論理式からプログラムへ
さて、論理式はわかったと思います。では本題のプログラムに戻していきましょう。まず、xとyで排他的論理和をとります。この値とxでもう一度論理和をとると、x^y^xとなり、xが得られる。こういう仕組みです。
実際に使うことはほぼない(一時変数に代入して入れ替える方が早いので)プログラムです。しかし、覚えておくとちょっとカッコいいです。自分のコードに入ってるとかなりイケてると思います。もちろん初見の人が混じりそうな複数人での開発で混ぜ込むと顰蹙ものですが。
