C++로 풀어보는 범위 내 두 수의 최대 XOR 값 구하기

문제 정의

주어진 범위 [L, R] 내에서 두 정수를 선택할 때, 가능한 모든 조합 중 XOR 값이 가장 큰 경우를 찾는 문제입니다.

예를 들어 범위가 L = 1, R = 21로 주어진 경우 출력값은 31이 됩니다. 31은 15와 16을 XOR 연산한 값으로, 해당 범위에서 얻을 수 있는 최대 XOR 값입니다.

접근 방식

이 문제는 L과 R을 XOR 연산한 결과의 최상위 비트(MSB)를 활용하면 간단하게 해결할 수 있습니다. L ^ R의 결과에서 가장 높은 비트가 1인 위치를 찾으면, 그 위치부터 하위 비트까지 모두 1로 채운 값이 곧 최대 XOR 값이 됩니다. 그 이유는 해당 비트 위치에서 L과 R의 값이 서로 다르다는 의미이며, 따라서 범위 내에서 그 비트를 1로 만들 수 있는 두 수의 조합이 반드시 존재하기 때문입니다.

알고리즘 단계

1. L ^ R 값을 계산합니다.
2. 이 값의 최상위 비트(MSB) 위치를 구한 뒤, 해당 위치부터 모든 하위 비트를 1로 채워 최종 결과를 만듭니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
int getMaxXOR(int L, int R){
    int LXR = L ^ R;
    int msbPos = 0;
    while (LXR) {
        msbPos++;
        LXR >>= 1;
    }
    int maxXOR = 0;
    int two = 1;
    while (msbPos--) {
        maxXOR += two;
        two <<= 1;
    }
    return maxXOR;
}
int main(){
    int L = 1;
    int R = 21;
    cout << "Result = " << getMaxXOR(L, R) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Result = 31

복잡도 및 정리

이 알고리즘은 L ^ R 값에서 MSB 위치를 찾는 데 O(log N), 결과를 구성하는 데 O(log N)의 시간이 소요되므로 전체 시간 복잡도는 O(log N)입니다. 범위 내 모든 쌍을 일일이 확인하는 브루트 포스 방식(O(N²))과 비교하면, 범위가 클 때도 매우 빠르게 동작하는 효율적인 풀이법입니다.