XOR SWAPの証明方法がわかりません。

Question

XOR SWAPの実装

XOR SWAPを知りました。教わったswapは、一時変数を用意して、交換対象の変数の一方を格納するやり方ですが、XOR SWAPは一時変数を使わないやり方だそうです。Scalaで関数を書いて試したところうまく動作しました。

def swap(a:Int, b:Int):(Int,Int) = {
    var l = a; var m = b
    l = l ^ m
    m = l ^ m // xor(xor(a,b),b) 復号したa 以下を参照してください。
    l = l ^ m // xor(xor(a,b),a) 復号したb
    (l,m)
}

なぜそうなるのか

ソースコードは3回、XORを取っているだけです。調べてみたところ以下を証明すれば良いことがわかりました。

xor(xor(a,b),b) = a あるいは xor(xor(a,b),a) = b

直感的には、XORを使って暗号化と復号ができるので、次のように解釈しました。
暗号化: xor(a,b) 平文aを鍵bで暗号化する。(平文bを鍵aで暗号化する)
復号： xor(xor(a,b),b) 平文aを鍵bで暗号化した暗号文を鍵bで復号して、元の平文aを得る。

証明

ちゃんとした証明がわかりません。よろしくお願いします。

真理値表

お二人の回答で教わったとおり、真理値表を作りました。

a	b	xor(a,b)	xor(xor(a,b),b)	xor(xor(a,b),a)
0	0	0	0	0
0	1	1	0	1
1	0	1	1	0
1	1	0	1	1

確かに、「xor(xor(a,b),b) = a あるいは xor(xor(a,b),a) = b」になりました。
これは証明なのですね。私は代数的な証明を考えていました。代数的な証明はできますか。

交換律

教えていただいた3つの規則に交換律を足して4つにします。
xor(a,b) = xor(b,a)

xor(xor(a,b),a) = bの証明は以下のとおり。

xor(xor(a,b),a)
= xor(xor(b,a),a) 交換律
以下省略

蛇足ですが、xor(1,a) = not(a) なのがわかりました。自力で考えられたので嬉しいです。

Answer 1

どこまで前提としていいのかわかりませんが、

(a^b)^b
= a^(b^b)
= a ^ 0
= a

Comments

[退会済みユーザー]

ありがとうございます。すでにベストアンサーを選んでしまいましたが、私の望んだ回答です。

Answer 2

XORの真理値表は4通りしかありません。ビットが増えても、これをただ並べただけになります。

|A|B|A^B|
|:==:|:==:|:==:|
|0|0|0|
|0|1|1|
|1|0|1|
|1|1|0|

あとは、4通りどれでも成立するか確認するだけです。「ちゃんとした証明」がどのようなものを言うのかわかりませんが、「全部調べる」のも立派な方法の1つです。

Comments

[退会済みユーザー]

ありがとうございます。真理値表を書くやり方を知りました。

Answer 3

こんな真理値表を埋めれば良いんじゃないでしょうか。

a	b	a XOR b	(a XOR b) XOR b	(a XOR b) XOR a)
0	0	...	...	...
0	1	...	...	...
1	0	...	...	...
1	1	...	...	...

別解

ブール演算でやるならこんな感じです。

(a XOR b) XOR b
= a XOR (b XOR b)  # 結合律
= a XOR 0  # (b XOR b)は0
= a # a XOR 0はa

Comments

[退会済みユーザー]

ありがとうございます。ブール演算で３つの規則を使っていることがわかりました。結合律と(a xor a) = 0と(a xor 0) = aですね。それぞれの証明を考えてみます。