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 整数型ではうまくいかないことに注意しましょう。

• Rust, u128
• C++, bitset<100>