はじめに

プログラムにおいて2つの変数の値を入れ替えるための手法として、一時変数を用意して処理を行うというものがあります。しかし、実は、一時変数なしで値を入れ替える事のできるXOR交換アルゴリズムというものがあります。これによって、リソースを節約することができます。本記事では、アルゴリズムの証明をブール代数により行います。

アルゴリズムの概要

めっちゃシンプルです。入れ替えたい変数を$x$と$y$とします。

$x \gets x\otimes y$
$y \gets x\otimes y$
$x \gets x\otimes y$

アルゴリズムの証明

まずは、排他的論理和$\otimes$の意味を復習しましょう。

$$A\otimes B= \overline{A}\cdot B+A\cdot \overline{B}$$

です。したがって、すべての計算を終えた後の$y$に注目すると、ド・モルガンの定理を用いて、

$$\gdef\n#1{\overline{#1}} \begin{aligned} y&\gets(x\otimes y)\otimes y=(\n{x}\cdot y+x\cdot \n{y})\otimes y=(\n{\n{x}\cdot y+x\cdot \n{y}})\cdot y+(\n{x}\cdot y+x\cdot \n{y})\cdot\n{y} \\ &=(x+\n{y})\cdot (\n{x}+ y)\cdot y+x\cdot \n{y}=x\cdot y \cdot (\n{x}+ y)+x\cdot \n{y}\\ &=x\cdot y+x\cdot \n{y}=x\cdot(y+\n{y})=x \end{aligned}$$

ということが分かります。次に、全ての計算を終えた後の$x$に注目すると、同じ式変形によって、

$$\begin{aligned} x&\gets (x\otimes y)\bigl((x\otimes y)\otimes y\bigr)=(x\otimes y)\otimes x=(y\otimes x)\otimes x=y \end{aligned}$$

が分かります。これによって、2つの変数の値が入れ替わる事が証明できました。

おわりに

現代のプロセッサではこのアルゴリズムの恩恵を受けることは限定的なようです。これに関しては、Wikipediaを御覧ください。