(多分)使えない論理演算メモ

・

(a | b) - (a ^ b) = (a & b)

某所のアセンブラの練習問題の答え(苦笑)

左辺の式から3行も減らせるぞ！(謎)

これで正解…のはず。



・

swap( int a, int b )

{

    a ^= b;

    b ^= a;

    a ^= b;

}

C言語における値の交換(いわゆる「swap」？)。

(本当は引数をポインタなり何なりにしないとダメなんですが、とりあえず無視で(何))

Cでは変数同士の値の交換が出来ないので、

値を交換したいときは大体、

int temp = a;

a = b;

b = temp;

こんな感じで別の変数を用意してやって値を交換するんですが、

前述の方法だと新しい変数の宣言なしで交換出来るそうです。



　以下、「値の交換」の方の余談。

　…どうもXORx3で交換出来るのが腑に落ちないので、

証明できないか考えてみる。

…あ、昔の記事で「XORで指定したビットだけ反転させる」とかやってるな。

何かに使えるかも。

…というか、指定したビットだけ反転できるんだから、二回反転したら元に戻る(=打ち消し合う)という解釈が使える…のかな？



　…何はともあれ、最終的にそれぞれの変数に何が入っているかを考えてみる。

a = (a ^ b) ^ (b ^ (a ^ b));

b = b ^ (a ^ b);

…とりあえずaは面倒臭そうなので、bの方から考えてみる(汗)

確かXORは交換法則が成り立つから、

「b = (a ^ b) ^ b;」

さっき言っていた「二回反転で元に戻る」というのを使えば、

「b = a;」

　同様に、aの方も整理してみる

「a = (a ^ b) ^ ((a ^ b) ^ b);」　　(交換)

「a = (a ^ b) ^ (a);」　　(打ち消し)

「a = (b ^ a) ^ a;」　　(交換)

「a = b;」　　(打ち消し)

　…というわけで、きちんと値の交換が出来ているわけですか。

変数にビットを反転させて潜ませておく…ということになるのかな。

…その発想は無いなぁ…(汗)



　修正 : 08/01/31 22:28

「b = a;」→「b = temp;」に修正