[Codeforces] Codeforces Round #676 (Div. 2) A. XORwice

2020年10月18日2020年12月12日

問題

方針

排他的論理和は \( 1 \oplus 1 = 0 \)、\( 0 \oplus 1 = 1 \) となるので、\( a, b \) の \( i \) ビット目を \( a_i, b_i \) とすると、\( a_i = 1 \wedge b_i = 1\) であるとき、\( x_i =1 \) とすると

\[ a_i \oplus x_i + b_i \oplus x_i = 0 \]

となります。 したがって、\( a, b \) の \( i \) ビット目がともに \( 1 \) であるとき、

\[ x \leftarrow x + 2^{i – 1}\]

とします。

コード

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

int a, b;

void solve() {
    int x = 0;
    for (int i = 0; i < 31; i++) {
        int t = (1<<i);
        if ((t & a) && (t & b)) x += t;
    }
    cout << (a ^ x) + (b ^ x) << "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> a >> b;
        solve();
    }
    return 0;
}