XOR SWAPの実装
XOR SWAPを知りました。教わったswapは、一時変数を用意して、交換対象の変数の一方を格納するやり方ですが、XOR SWAPは一時変数を使わないやり方だそうです。Scalaで関数を書いて試したところうまく動作しました。
Scala
1def swap(a:Int, b:Int):(Int,Int) = { 2 var l = a; var m = b 3 l = l ^ m 4 m = l ^ m // xor(xor(a,b),b) 復号したa 以下を参照してください。 5 l = l ^ m // xor(xor(a,b),a) 復号したb 6 (l,m) 7}
なぜそうなるのか
ソースコードは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) なのがわかりました。自力で考えられたので嬉しいです。
回答3件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2018/11/30 07:08