XOR 交換アルゴリズムと一時変数を使ったスワップ
先日本を読んでいて、スワップのコードを見たときに XOR 演算を使って一時変数を使わずに変数の中身を交換する事が出来る事を思い出し、wikipedia 巡りをしていました。
最近のプロセッサ事情では XCHG 命令一発で交換できるらしく、実は XOR 交換アルゴリズムを用いた値の交換の方が遅い事があるそうです。
という事で実際に計測してみるべくコード書いて試してみました。
gist: xor exchange algorithm
$ gcc -o xor_exchange xor_exchange.c $ time ./xor_exchange SWAP: x: 1, y: 2 2.646 secs $ time ./xor_exchange --xor-change XOR_CHANGEx: 1, y: 2 7.528 secs
1000,000,000 回の繰り返しを実行した結果が上記の処理時間ですが、XOR 交換よりも一時変数を用いたスワップの方が高速に処理されてました。複雑なアルゴリズムを使った高速な計算や、理解に苦しむプログラムの書き方によって高速化を狙うとかはよくありそうな話ですが、もしかしたら他の計算もこんな感じで昔とは事情が違っているのかもしれないんですね。
