ビット演算>xor(排他的論理和)を使った値の交換

ここまでは基礎編だったが、ここからは中級編だ。少し難しくなるかもしれない。
が、マスターすれば便利な機能なので、ぜひマスターしてワンランク上のビット演算氏になってもらいたい。

排他的論理和 のところで一応説明したのだが、もう一度書いておくと、排他的論理和には以下の様な性質がある。

  • x ^ 0 = 0 ^ x = x   // 0 との排他的論理和は値を変えない
  • x ^ x = 0    // 同じものを xor すると結果は 0
  • (x ^ y) ^ z = x ^ (y ^ z)   // 結合法則
  • x ^ y = y ^ x    // 交換法則

なので、 (x ^ y) ^ x = (y ^ x) ^ x = y ^ (x ^ x) = y ^ 0 = y となる。

この性質を使うと、下記のコードで2つの変数を入れ替えることが出来る。

int x = 何らかの値;
int y = 何らかの値;
x ^= y;
y ^= x;
x ^= y;

狐に摘まれた方も少なくないと思うが、上記のコードで x, y に入っている値はしっかり入れ替わる。

x,y の初期値を x0, y0 として説明する。
最初に x ^= y; を実行すると、x には x0 ^ y0 が入る。
次に y ^= x; を実行すると、y0 ^ (x0 ^ y0) = x0 なので、y には x の初期値 x0 が入る。
次に x ^= y; を実行すると、x には (x0 ^ y0)、y には x0 が入っているので、(x0 ^ y0) ^ x0 = y0 となり、x には無事 y0 が入り、x と y の値が交換されることになる。

ご理解いただけたであろうか?

演習問題:

  1. 変数の値を入れ替えるコードをビルド・デバッガで実行し、本当に中身が入れ替わることを確認しなさい。