ビット演算>排他的論理和

排他的論理和とは xor のことだ。C/C++ の式では、二項演算子として 「^」 記号を使用する。

1ビットの場合、論理和演算結果は以下のようになる。

A B A ^ B
0 0 0
0 1 1
1 0 1
1 1 0

A, B が入力で、A ^ B のカラムが演算結果だ。

排他論理和の場合、入力が両方0または両方1の時の結果が0で、片方が1の場合の結果は1になる。
通常の足し算で、桁上りを無視したものと思えばよい。

重要な視点は、

  • Aが1の場合は、Bの反転が結果になる。
  • Aが0の場合は、Bの値がそのまま結果になる。

ということである。

「A ^ B」 と 「B ^ A」 の結果は同じ値だ。交換則が成立している。
なので、以下のようにも言える。

  • Bが1の場合は、Aの反転が結果になる。
  • Bが0の場合は、Aの値がそのまま結果になる。

上記を数式で書くと以下のようになる(※ ~X は後で解説するが、反転を表す)。

X ^ 1 = 1 ^ X = ~X
X ^ 0 = 0 ^ X = X

また、自分自身との排他的論理和は常に 0 となる。

x ^ x = 0

「(a ^ b) ^ c = a ^ (b ^ c)」という結合法則も成り立つ。なので、同じ値を2回排他的論理和演算しても値は変化しないことになる。

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

交換法則も考慮すれば、以下の式も成り立つ。

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

この特徴は非常によく利用されるので、ぜひ覚えて欲しい。

これまでの説明は1ビットのみであったが、ビットがたくさんある場合はどうなのであろうか?

C/C++ では 変数と整数の論理和がよく使用される。変数が int 型の場合32ビットとかで、1ビットではなく多ビットだ。
で、「多ビットの値どうしの排他的論理和は、各ビットごとに計算される。」ということだ。

例えば、0b10101010 と 0b00001111 との排他的論理和をとると、0b10100101 となる。
※ 0b は2進数を表す前置記号で、C++14 から使用できる。

ここで先ほどの視点を思い出して欲しい。

入力の2番めは上位4ビットが0で、下位4ビットが1だ。1と排他的論理和を取るとビットが反転し、,0と論理和をとると、1番目の値がそのまま結果にあらわれているのが分かるだろうか?

これを業界用語で、2番めの値の ビットを反転する と呼ぶ。
つまり、排他的論理和により、ビット列の指定箇所だけを反転することが出来るということだ。

演習問題:

  1. int x; になんらかの値が入っている時、xの下位8ビットを反転するコードを書きなさい