[yukicoder] No. 0939 and or

2019年12月4日2019年12月23日

問題

方針

\( X, Y \) を \( 2 \) 進数で表現したときの \( i \) 番目のビットを \( x_i, y_i \) とします。同様に \( A, B \) についても \( a_i, b_i \) とします。条件より、\( x_i \wedge y_i = a_i \) かつ \( x_i \vee y_i = b_i \) となります。

\( a_i = 1 \wedge b_i = 0 \) を満たす \( x_i. y_i \) は存在しません。これは、\( x_i \wedge y_i = 1 \) のとき、\( x_i = 1 \wedge y_i = 1 \) であり、このとき、\( x_i \vee y_i = 1 \) となるからです。つぎに、\( a_i = 0 \wedge b_i = 0 \) のときは、\( x_i = 0 \wedge y_i = 0 \) となります。つぎに、つぎに、\( a_i = 1 \wedge b_i = 1 \) のときは、\( x_i = 1 \wedge y_i = 1 \) となります。

最後に、\( a_i = 0 \wedge b_i = 1 \) のとき、\( x_i = 1 \wedge y_i = 0 \) または \( x_i = 0 \wedge y_i = 1 \) の \( 2 \) 通りあります。この条件を満たすビットの数を \( c \) とすると、答えは、\( \max(1, \ 2^{c – 1} ) \) となります。 \( 2^{c – 1} \) となっているのは、\( X \leq Y \) という条件から、\( a_i = 0 \wedge b_i = 1 \) を満たす最大の \( i \) について、\( x_i = 0 \wedge y_i = 1 \) となっていなければならないからです。

また、自然数 \( n \) の \( i \) 番目のビットが \( 0 \) かどうかは、\( n \wedge 2^{i} = 0 \) であることを確かめれば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll A, B;
    cin >> A >> B;
    ll t = 1;
    ll ans = 0;
    for (int i = 0; i < 31; i++) {
        ll u = A & t;
        ll v = B & t;
        if (u != 0 && v == 0) {
            cout << 0 << "\n";
            return 0;
        } else if (u == 0 && v != 0) {
            ans++;
        }
        t *= 2;
    }
    ans = max(ans, 1ll);
    cout << (1<<(ans - 1)) << "\n";
    return 0;
}