XOR Trick

C++ algorithm

　普通，変数x, yの中身を交換しようとした場合，テンポラリ変数を使って

int x=1, y=2, temp;
temp = x;
x = y;
y = x

というようにするしかないとずっと思っていた．

ところが世の中にはXOR trickというものがあるらしい．

x^=y; (1)
y^=x; (2)
x^=y; (3)

なんだこりゃーー！！誰だこんなこと考えたやつ！
っていうか知らなかった自分も自分だ．

ちょっと考えてみる．

X = X ^ Y ----(1)'
Y = Y ^ X = Y ^ (X ^ Y) = (X ^ Y) ^ Y = X ^ (Y ^ Y) = X ^ 0 = X ----(2)'
X = (X ^ Y) ^ X = Y -----------(3)'

具体例：
x = 10010, y = 00101;

x = 10010 ^ 00101 = 10111
y = 00101 ^ 10111 = 10010
x = 10111 ^ 10010 = 00101

うわ，すげえ！これヤバイって！誰だよ考えたの！

という具合にテンションがあがったのでC++の関数にした．

template<class T>
void xorTrick(T& x, T& y)
{
	x^=y;y^=x;x^=y;
}

int main()
{
	int x = 24, y = 81;
	cout <<"Before swapping: x="<< x << " y="<< y <<endl;

	xorTrick<int>(x, y);

	cout <<"After swapping: x="<< x << " y="<< y <<endl;
	return 0;
}

無駄にテンプレート．ビット演算が使える型じゃないと駄目です．
でプログラム書いてて思ったんですが，swapする値が（同じ値じゃなくて）同じ"変数"だとしたら，
つまり上のコードならxorTrick<int>(x,x)みたいに呼ぶと

X = X ^ X = 0 ----(1)'
X = 0 ^ 0 = 0 ----(2)'
X = 0 ^ 0 = 0 -----(3)'

だめじゃん．同じ変数で呼ばないようにっていう制約とかってつけられないんですか．プログラム詳しい人．

　で，ここまでやってから検索したら，普通に知られていることなんですね，この問題．
普通にWikiにのってる…XOR交換アルゴリズム
見事なまでに車輪の再発明チックだなぁ．や，別に何も発明していませんが．


　ついでに，交換アルゴリズムは色々あるのだということを今日知った．
おもしろい解析をしているサイトを見つけたのでここにリンクしときます．
さっき僕が書いたコードみたいな単純なケースなら，-O2で最適化したらみんな一緒．
アセンブリ見るところまでやろうと思わないなぁ．すごいなぁ．




　多分情報科学をちゃんと勉強した人にとっては常識なんでしょうねぇ．
こういうの見ると，僕もヒネクレずに大学情報系行っとけば楽しかったのかなぁとおもったり．
やっぱ自分，アルゴリズムが大好きなのだなぁと思った今日．