XORでの交換

結論

読みにくいし、たいして速くもならないしので無理に使う必要もない。
ただし、書き方は理解しておくべきであり、非常に短く書けるので、競技プログラミングや自分だけが使うテストコードなど、いわゆる「捨てコード」では使えた方が良い。開発現場であれば周囲の環境に合わせるべきである。例えば頻繁に人が入れ替わる場合はたいてい初心者が来るので書くべきではないが、特に入れ替わりもなく、実力者ぞろいの環境であればどんどん使うべきである。

概要

変数を交換する際には一般的には以下のように変数を新たに一つ用意して交換を行う。

void swap(int& a, int& b) {
	int c = a;
	a = b;
	b = c;
}

これをXORを使用することで、以下のように短く書くことができる。

void swap_xor(int& a, int& b) {
    a = a^b;
    b = a^b;
    a = a^b;
}

//さらに短くするとこうなる
void swap_xor(int& a, int& b) {
    a ^= b ^= a ^= b;
}

これはXORの以下の２つの性質を利用している

1.x^x＝0　ある同一の変数xのXORを取ると0となる
2.(a^b)^c = a^(b^c) XORを取る順番は結果に無関係である。つまり、順番を変えても同一になる。 （代数学では「結合律を満たす」という）

このうち、1.は定義なので自明とする。
2.において、ある変数a,b,cがあったとして、cにaとbのXORの結果を代入したとする。

int c = a^b

この時cに対してさらにaのXORを取れば結果はbになり(a^b^a => b)、
逆にこの時cに対してさらにbのXORを取れば結果はaになる(a^b^b => a)。
これらのことをを利用する。

c = a^bの時、
c^a ＝a^b^aであり、
a^a=0であるから
結局c^a = 0^b=bとなる

これらの性質を用いて説明する。実際にはcという変数を用意せず、aという変数にa^bの結果を代入しているため、わかりにくくなっている。ポイントはa,bという変数に格納されている値が何かを丁寧にみていくと理解できる。

void swap_xor(int& a, int& b) {
    a ^= b; //a^bの結果をaに代入
    b ^= a; //a(ここでは中身はa^b)とbのXORを取る。bにはb^a^bの結果、つまりa(0^a)を代入している。b^b=0を使用する。
    a ^= b; //a(同じく中身はa^b)とb(中身はa)なので、a^b^aの結果、つまりb(0^a)をaに代入している。a^a=0を使用する。
}

速度比較

各５回ずつ実行して比較したのだが、ほぼ同じ。

swap by XOR = 1.876sec.
swap by XOR = 1.833sec.
swap by XOR = 1.826sec.
swap by XOR = 1.8sec.
swap by XOR = 1.82sec.
swap by variable = 1.803sec.
swap by variable = 1.811sec.
swap by variable = 1.81sec.
swap by variable = 1.827sec.
swap by variable = 1.86sec.

以下比較用コード

# include <iostream>
# include <time.h>
using namespace std;
# define rep(i,s,n)for(ll i = s;i<n;i++)

void swap(int& a, int& b) {
	int c = a;
	a = b;
	b = c;
}

void swap_xor(int& a, int& b) {
    a ^= b ^= a ^= b;
}

int main() {
    int a = 10;
    int b = 20;

    clock_t start,end;

    for (int k = 0; k < 5; k++) {
        start = clock();
        for (int i = 0; i < 1e8; ++i) {
            swap_xor(a, b);
        }
        end = clock();
        std::cout << "swap by XOR = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
    }
    for (int k = 0; k < 5; k++) {
        start = clock();
        for (int i = 0; i < 1e8; ++i) {
            swap(a, b);
        }
        end = clock();
        std::cout << "swap by variable = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
    }
}