Bitwise ORの最大化・最小化

以下の問題を解いていたときに考えたことです。

atcoder.jp

この問題はbitwise orとしてありうるものを数える問題ですが、今回は最小値と最大値を求めることを考えます。

問題

整数が与えられます。以上以下の整数から1個以上選んで、それらのbitwise orを取ってできる整数としてありうるもののうち、最大値と最小値を求めてください。

制約

• (元の問題と同じ制約にしています)

考察

のときはしか作れないのでどちらもです。以下ではの場合を考えます。

最小値について
bitwise ORを取ることによって数が小さくなることはないので、個だけ選ぶ場合を考えれば良いです。この場合の最小値は明らかにです。

最大値について
bitwise ORを取ることによって数が小さくなることはないので、答えはからまでの全ての数のbitwise ORです。これを求めることを考えます。とが上位桁まで一致していたとします。そうすると以上以下の全ての数の上位桁もこれに等しいので、答えの上位桁はこれと等しいです。

残りの桁はどうなっているでしょうか。実は(?)残りの桁は全てになっています。なぜならの上から番目の桁はで、さらにとの間に桁以下の桁が全てとなるような数が存在するからです。

実装

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

using lint=long long;

int main()
{
   lint A,B; cin>>A>>B;
   if(A==B){ cout<<A<<' '<<B<<endl; return 0; }

   lint mn=A,mx=B;
   const int LOG=60;
   for(int i=LOG-1;i>=0;i--){
      if((A>>i&1)!=(B>>i&1)){
         for(int j=i-1;j>=0;j--) mx|=1LL<<j; 
         break;
      }
   }
   cout<<mn<<' '<<mx<<endl;
   return 0;
}

感想

どちらもbitwise ORを取って数が小さくなることはないという事実から分かるのが面白いと思いました。元の問題ではbitwise ORの最小値と最大値を求めることを何度かする必要があるので、一番小さい数が最小値、全部のORが最大値になるということが分かっていれば少し見通しが良くなるかなと思いました。