C++で範囲内のすべての整数のビットごとのOR（|）を効率的に計算する方法

この問題では、2つの整数値 a と b が与えられ、a から b までの範囲に含まれるすべての整数のビットごとのOR（|）を求めることが課題となります。つまり、a | a+1 | a+2 | … | b-1 | b の値を計算する必要があります。

問題の例

入力 − a = 3、b = 8

出力 − 15

解説 − 3 | 4 | 5 | 6 | 7 | 8 = 15

シンプルな解法

最も単純な解法は、a から開始し、1ずつ増やしながら b までのすべての数値のビットごとのORを順番に計算していく方法です。この方法は理解しやすい反面、範囲が大きくなると計算時間が長くなるという欠点があります。

より効率的な解法

最上位ビット（MSB）を利用することで、より効率的に計算できます。手順は以下の通りです。

ステップ1 − a と b のそれぞれについてMSBの位置を求めます。これらを MSBa および MSBb とします。

ステップ2 − MSBa と MSBb が等しいかどうかを確認します。

ステップ2.1 − MSBa と MSBb が等しい場合は、次のように処理します。

ステップ2.1.1 − 結果の該当するMSB位置のビットを1に設定します。

ステップ2.1.2 − a と b からそのMSBの値を引き、得られた値を新しい a と b としてステップ1に戻ります。

ステップ2.2 − MSBa と MSBb が等しくない場合は、次のように処理します。

ステップ2.2.1 − 結果の0ビット目から max(MSBa, MSBb) ビット目までのすべてのビットを1に設定します。

ステップ3 − 結果を出力します。

アルゴリズムの動作例

例 − a = 3、b = 8 の場合

手順 −

ステップ1 − MSBa = 1、MSBb = 3

ステップ2 − MSBa ≠ MSBb であるため、結果のビット位置3からビット位置0まですべて1に設定します。result = (1111)₂ = 15 となります。

C++での実装コード

それでは、この問題を解くためのコードを見てみましょう。

#include <iostream>
using namespace std;
int FindpositionMSB(long long int n){
   int MSBval = -1;
   while (n) {
      n = n>>1;
      MSBval++;
   }
   return MSBval;
}
long int CalcBitwiseORRaneg( long int a, long int b) {
   long int result = 0;
   int msba = FindpositionMSB(a);
   int msbb = FindpositionMSB(b);
   while (msba == msbb) {
      long int value = (1 << msba);
      result += value;
      a -= value;
      b -= value;
      msba = FindpositionMSB(a);
      msbb = FindpositionMSB(b);
   }
   msba = max(msba, msbb);
   for (int i = msba; i >= 0; i--) {
      long int res_val = (1<<i);
      result += res_val;
   }
   return result;
}
int main() {
   long int a = 3, b = 8;
   cout<<"The bitwise OR (|) of all integers in the range from "<<a<<" to "<<b<<" is "<<CalcBitwiseORRaneg(a, b);
   return 0;
}

出力

The bitwise OR (|) of all integers in the range from 3 to 8 is 15