C++로 범위 내 모든 정수의 비트 OR 값 구하기

이 문제에서는 두 개의 정수 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단계 − 두 값이 같다면 다음을 수행합니다.

2.1.1 − 결과(result)의 해당 MSB 자리를 1로 설정합니다.

2.1.2 − a와 b에서 MSB 값을 뺀 후 새로운 a, b로 만들고 다시 1단계로 돌아갑니다.

2.2단계 − 두 값이 다르다면 다음을 수행합니다.

2.2.1 − 결과의 0번째 비트부터 max(MSBa, MSBb)번째 비트까지 모두 1로 설정합니다.

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

알고리즘 동작 예시

a = 3, b = 8인 경우를 단계별로 살펴보겠습니다.

1단계 − MSBa = 1, MSBb = 3

2단계 − MSBa ≠ MSBb이므로, 결과의 0번째 비트부터 3번째 비트까지 모두 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<<"3부터 "<<b<<"까지 범위의 모든 정수의 비트 OR(|) 값은 "<<CalcBitwiseORRaneg(a, b);
    return 0;
}

출력 결과

3부터 8까지 범위의 모든 정수의 비트 OR(|) 값은 15