XORによる2変数の交換

修士2年の佐賀美です

研究の息抜きにゲーム開発会社のブログを見ていたところ、面白い記事がありました

記事によると、XORを使って2つの変数を入れ替えるそうです

ブログがリンクフリーかどうかわからないのでwikipediaのリンクを載せます

http://ja.wikipedia.org/wiki/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%90%86%E5%92%8C

この方法はプログラムにも応用でき、一時変数を使わずに2変数を交換できるそうです

普通は、AとBの値を入れ替えるプログラムは下のように書きます

int A = 1, B = 2, tmp;

tmp = A;

A = B;

B = tmp;

しかし、XORを使うことで、下のようにも表現できるそうです

int A = 1, B = 2;

A ^= B;

B ^= A;

A ^= B;

プログラムだと直感的にわかりづらいため、ベン図を書きました

XORを使ったプログラムの1行目、つまり、AとBのXORは下の図になります

一番大事な点は、AとBの共通部分が0になっているということです

XORを使ったプログラム2行目の結果は下の図になります

プログラム1行目の結果とBのXORをとると、Bとの共通部分が無くなり、Bと共通で無い部分(中央の虫食い部分)が追加されます

最後にXORを使ったプログラム3行目の結果は下の図になります

今度はAとの共通部分が消え、中央の虫食い部分が追加されます

(ちなみに、今回はベン図を使いましたが、実際にはもっとパターンがあります(AとBが排反の場合など))

このように、XORのみで2変数の交換ができるそうです

さらに、暗号にも使われているそうです(バーナム暗号)

息抜きのつもりが、結構勉強になりました

カテゴリー: 未分類