[yukicoder] No. 0939 and or

問題

方針

\( 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 \) であることを確かめれば良いです。

コード