C++에서 범위의 비트 OR(또는 -)

이 문제에서는 두 개의 정수 값과 b가 제공됩니다. 그리고 우리의 임무는 범위에서 b까지의 비트 OR(|)을 찾는 것입니다. 이것은 우리가 |의 값을 찾아야 한다는 것을 의미합니다. +1 | +2 | … b-1 | 나.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - a =3, b =8

출력 − 15

설명 − 3 | 4 | 5 | 6 | 7 | 8 =15

문제를 해결하기 위해 간단한 솔루션은 에서 시작하여 1을 b로 증가시켜 모든 숫자의 비트별 OR을 찾는 것입니다.

더 효과적인 솔루션

이것은 보다 효과적인 솔루션이며 −

1단계 − 와 b 모두에 대한 MSB 비트를 찾습니다. MSBa 및 MSBb라고 가정하겠습니다.

2단계 − MSBa가 MSBb와 같은지 확인합니다.

2.1단계 - MSBa와 MSBb가 동일한 경우. 하세요

2.1.1단계 − 결과의 MSB를 1로 설정합니다.

2.1.2단계 - 및 b에 대한 새로운 값이 될 및 b에서 MSB를 뺍니다. 1단계로 이동합니다.

2.2단계 - MSBa와 MSBb가 같은 경우. 하세요

2.2.1단계 − 결과의 모든 비트를 0부터 최대(MSBa, MSBb)까지 설정합니다.

3단계 − 결과를 출력합니다.

이제 위의 알고리즘이 작동하는 것을 봅시다 -

예 - a =3 및 b =8.

해결책 -

1단계 - MSBa =1; MSBb =3

2단계 − MSBa !=MSBb, 결과의 비트 위치 3에서 비트 위치 0까지의 모든 비트를 1로 설정합니다. 결과 =(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