はじめに
みなさんはXOR(eXclusive OR, 排他的論理和)を使っているでしょうか? 排他的論理和は論理演算の中でも難しいと言われているので難しく感じるかもしれませんが、すごく応用が利きます。
XOR
XORは入力をx, yとしたとき、xとyが同一なら0、違えば1を出力します。
x | y | 結果 |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
XORの特性として、2回同じ値でXORをとると元に戻ります。
例:
01101 10101 ------ 11000 ←1回目の計算結果 10101 ------ 01101 ←2回目の計算結果
また、x ^ y = zのとき、x ^ z = yとy ^ z = xを満たします。
使用例
使用例を見ていきましょう。
チェックサム
データが正しいかどうか調べるときに、一定の長さごとにXORをとって、全て0ならば、 そのデータは正しいと言えます。
XOR交換
XORを用いることにより、一時変数を用いずに値の交換が可能です。 x ^ y = zならばx ^ z = yとy ^ z = xを利用しています。
x = x ^ y; y = x ^ y; x = x ^ y;
1行目でxにx ^ y、つまりzが代入されます。
2行目でyにz ^ y、つまりxが、3行目でxにz ^ x、つまりyが代入されることになります。
一時変数を使わないのでメモリを節約できますが、CPUなどによっては一時変数を用いたほうが早いことがあるようです。
XOR暗号
2回同じ値でXORをとることで元に戻る特性を利用することにより、暗号鍵と復号鍵が同一な暗号を作成できます。
単一換字式暗号で暗号強度はとても弱いですが、非常に簡単に実装できます。
Xorshift
Xorshiftは擬似乱数生成アルゴリズムの一種で、実装が簡単で、高速です。
wikipediaに実装例が載っているのでそちらをどうぞ。
最後に
XORは非常に単純ながら、様々なことに応用できます。
論理回路を学んだとき、XORは便利と聞いて、何が便利なのか疑問に思っていましたが、実際便利です。
もしかすると、将来の技術もXORを利用する技術かもしれません。