A - Intersection Editorial by rsk0315
Note: A 問題の解説を欲している人向けではないかもしれません。中級者向けの別解かも。
下から l
-bit 目以上 r
-bit 目未満が 1
で、他が 0
であるような整数は、
!(!0 << (r - l)) << l
(1 << r) - (1 << l)
!0 << r ^ !0 << l
などで得られます(!
はビット反転。言語によっては ~
)。
そこで、\((L_1, R_1)\) と \((L_2, R_2)\) の両方について上記の値を求め、bitwise-AND を求めたものを考えます。このうち 1
であるビットの個数が、求める値となります。
上限が \(100\) なので 64-bit 整数型ではうまくいかないことに注意しましょう。
posted:
last update: