C++에서 주어진 범위 내 최대 비트 AND 쌍 찾기

문제 설명

범위 [L, R]이 주어졌을 때, L ≤ X < Y ≤ R 조건을 만족하는 모든 가능한 쌍 (X, Y) 중에서 X & Y(비트 AND 연산 결과)가 가장 큰 쌍을 찾아, 그 비트 AND 값을 출력하는 것이 이번 문제의 목표입니다.

예시

예를 들어 L = 1, R = 10일 경우, 최대 비트 AND 값은 8입니다. 이는 다음과 같이 계산됩니다.

1000  # 8의 이진 표현
AND (&)
1001  # 9의 이진 표현
----
1000  # 최종 결과 = 8

여기서 8과 9는 범위 [1, 10] 안에 속하는 두 수이며, 두 수의 비트 AND 연산 결과인 8이 해당 범위에서 만들 수 있는 최댓값입니다.

알고리즘 접근 방법

가장 직관적인 방법은 브루트 포스(Brute Force) 기법입니다.

1. L부터 R까지의 모든 숫자 쌍 (i, j)을 탐색합니다. 단, i < j 조건을 유지하여 중복을 피합니다.
2. 각 쌍에 대해 i & j 연산을 수행합니다.
3. 지금까지 구한 최댓값보다 크면 최댓값을 갱신합니다.
4. 모든 쌍을 확인한 후 최종 최댓값을 반환합니다.

C++ 예제 코드

#include <bits/stdc++.h>
using namespace std;

int getMaxBitwiseAndValue(int L, int R) {
    int maxValue = L & R;
    for (int i = L; i < R; ++i) {
        for (int j = i + 1; j <= R; ++j) {
            maxValue = max(maxValue, (i & j));
        }
    }
    return maxValue;
}

int main() {
    int L = 1, R = 10;
    cout << "Maximum value = " << getMaxBitwiseAndValue(L, R) << endl;
    return 0;
}

출력 결과

Maximum value = 8

복잡도 분석

위 코드는 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(N²)입니다. 여기서 N은 범위의 크기(R − L + 1)입니다. 따라서 이 방법은 범위가 작은 경우에는 충분히 효율적이지만, 범위가 매우 커지면 실행 시간이 급격히 늘어날 수 있습니다. 이 경우 비트 연산의 특성을 활용한 최적화 기법으로 개선할 수 있습니다.