XOR

紹介

• 最近、XOR演算子を説明する機会があった。かつてはコンピュータで低レベルのビット操作を行うためにXORを学ぶことが必須だったが、現在では高水準プログラマにとっては選択事項になっている。
• XORに関する講義を準備しながらさまざまな考えを整理し、それを文書として残すことにした。

XORのブール論理

XORとは何か？

• XORは2つのビットを入力として受け取り、1つのビットを出力する論理演算子である。
• 真理値表によってXORの動作を説明できる。

「排他的OR」

• XORは「排他的OR」を意味し、2つの入力のうち片方だけが真のときに真を返す。

「等しくない」演算子

• XORは2つの入力が異なるときに1を返すため、a ≠ b と同じように動作する。

条件付き反転

• XORは、一方の入力が他方の入力を反転させるかどうかを決める条件付き反転演算として見ることができる。

パリティ、または2で割った余り

• XORは、入力のうち真であるビットの個数が奇数のときに1を返す。

2で割った差

• XORは、加算と減算を2で割った余りと同じように動作する。

XORの性質

• XORは可換法則と結合法則に従い、0は単位元として機能し、すべての入力は自己逆元である。

整数に対するビット単位XOR

• 整数を2進数で表現し、ビット単位でXOR演算を実行できる。
• ビット単位XORはブールXORと同じ性質を持つ。

XORの応用

暗号化: 平文とキーストリームの結合

• XORは暗号化で平文とキーストリームを結合するために使われる。
• XORはハードウェアでは加算より単純であるため効率的である。

ピクセルグラフィックス: 簡単に消せる図形の描画

• 1980年代のコンピュータグラフィックスでは、XORを使って簡単に消せる図形を描いていた。
• XORを使うと、ピクセルをもう一度描画して元の状態に復元できる。

「ハーフアダーの同一性」

• XORは加算の下位ビットを表し、ANDは上位ビットを表す。
• 整数に対してXORとANDを使って加算を行うことができる。

この文書はXORのさまざまな性質と応用を説明し、XORがどのように動作し、どこで有用に使えるのかを理解する助けとなる。