けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 213 A - Bitwise Exclusive Or (100 点)

XOR は 2 回やると元に戻る!!!(素振り!)

問題概要

非負整数  A, B が与えられます。

 A ^  C =  B

を満たす整数  C を求めてください。

制約

  •  0 \le A, B \le 256

XOR とは

XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事にて。

qiita.com

XOR は、まず 0 と 1 について定義すると下表のようになります。

0 1
0 0 1
1 1 0

つまり、「同じ物どうしだと 0」「違う物どうしだと 1」となります。一般の整数 a, b に対する XOR 和は次のように定義されます。たとえば a = 19、b = 14 としたとき、まずこれらを 2 進法で表します。

  • a = "10011"
  • b = "01110"

これらを各桁ごとに XOR 和をとります。そうすると、

a ^ b = "11101"

となります。これは 10 進法で表すと 29 に相当します。Python で確かめて見ます。

>>> a = 19
>>> b = 14
>>> a ^ b
29

XOR は 2 回やると元に戻る

これは XOR のもつすごい特徴です。一般に同じ整数を XOR をとると 0 になります。

a ^ a = 0

という感じです。そのようになる理由は、ニ進法で表したときにどの桁を見ても「0 と 0」か「1 と 1」になっているからです。続いて、このことから言えるのは、ある整数 b に他の整数 a を 2 回 XOR 和をとると元に戻るということです! つまり

b ^ a ^ a = b (b に戻る!)

が成り立ちます。これを踏まえて今回の問題を考えて見ましょう。

今回の問題

今回の問題は、 A C を足すと  B になるような  C を求める問題です。ここでは「足す」という言葉を「XOR 和をとる」という意味で使います。

 A ^  C =  B

この式の両辺に  A を足してみましょう!!! そうすると

 A ^  A ^  C =  A ^  B

というふうになります。そうすると、 A ^  A = 0 となって消えるので

 C =  A ^  B

となります。よって答えは A ^ B を出力すればよいということになります。

一次方程式とのアナロジー

今回の解法は少し突飛な発想に思えるかもしれませんが、中学校での一次方程式で習う「移項」はまさにこれに相当することをやっています。たとえば

 3 + x = 5

という方程式を解くときには、両辺から  3 を引きます。

 3 + x - 3 = 5 - 3

そうすると  3 - 3 = 0 となって消えるので

 x = 5 -3 = 2

と求められます。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    cout << (A ^ B) << endl;
}