C ++の範囲のビットごとのOR（または-）

この問題では、2つの整数値aとbが与えられます。そして、私たちのタスクは、aからbまでの範囲のビットごとのOR（|）を見つけることです。これは、|の値を見つける必要があることを意味しますa + 1 | a + 2 | …b-1| b。

問題を理解するために例を見てみましょう

入力 − a =3、b =8

出力 − 15

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

この問題を解決するための簡単な解決策は、aから開始し、1をbに増やして、すべての数値のビット単位のORを見つけることです。

より効果的なソリューション

これはより効果的な解決策です。これは-

ステップ1 − aとbの両方のMSBビットを見つけます。たとえば、MSBaとMSBbです。

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

ステップ2.1 −MSBaとMSBbが等しい場合。やる、

ステップ2.1.1 −結果のMSBを1に設定します。

ステップ2.1.2 −aとbの新しい値となるaとbからMSBを引きます。手順1に進みます。

ステップ2.2 −MSBaとMSBbが等しい場合。やる、

ステップ2.2.1 −結果の0からmax（MSBa、MSBb）までのすべてのビットを設定します。

ステップ3 −結果を印刷します。

さて、上記のアルゴリズムが機能しているところを見てみましょう-

例 − a=3およびb=8。

解決策 −

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

ステップ2 − MSBa！=MSBb、結果のビット位置3からビット位置0までのすべてのビットを1に設定します。result=（1111）2 =15

例

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

#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