XOR は 2 回やると元に戻る！！！(素振り！)
問題概要
非負整数 が与えられます。
^
=
を満たす整数 を求めてください。
制約
XOR とは
XOR 演算は、AND と OR と同じく、ビット (整数) 同士で定義される演算です。ビットについては次の記事にて。
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 に戻る！)
が成り立ちます。これを踏まえて今回の問題を考えて見ましょう。
今回の問題
今回の問題は、 に
を足すと
になるような
を求める問題です。ここでは「足す」という言葉を「XOR 和をとる」という意味で使います。
^
=
この式の両辺に を足してみましょう！！！ そうすると
^
^
=
^
というふうになります。そうすると、 ^
= 0 となって消えるので
=
^
となります。よって答えは A ^ B を出力すればよいということになります。
一次方程式とのアナロジー
今回の解法は少し突飛な発想に思えるかもしれませんが、中学校での一次方程式で習う「移項」はまさにこれに相当することをやっています。たとえば
という方程式を解くときには、両辺から を引きます。
そうすると となって消えるので
と求められます。
コード
#include <bits/stdc++.h> using namespace std; int main() { int A, B; cin >> A >> B; cout << (A ^ B) << endl; }
