C++ 배열에서 두 원소 쌍으로 만들 수 있는 최대 비트 AND 값 구하기

문제 개요

양의 정수 n개로 이루어진 배열이 주어졌을 때, 배열에서 임의의 두 원소를 골라 수행한 비트 AND(bitwise AND) 연산 결과 중 최댓값을 찾는 것이 목표입니다.

예시

입력 배열이 {10, 12, 15, 18}이라면, 만들 수 있는 비트 AND 값 중 최댓값은 12입니다. 실제로 12 AND 15 = 12이며, 다른 모든 쌍의 결과는 이보다 작습니다.

알고리즘 접근 방법

비트 AND 연산은 두 비트가 모두 1일 때만 1이 됩니다. 따라서 결과를 최대화하려면 가능한 한 높은 자리 비트(MSB)부터 1로 만드는 것이 유리합니다. 이 성질을 활용하면 다음과 같이 해결할 수 있습니다.

• 최상위 비트(MSB)부터 시작하여, 해당 비트가 설정된(set) 원소가 배열에 최소 2개 이상 존재하는지 확인합니다.
• 2개 이상 존재한다면 그 비트는 정답에 포함하고, 그렇지 않다면 해당 비트는 버립니다.
• MSB부터 LSB(32번째 비트부터 1번째 비트까지) 순서로 각 비트 위치를 검사하며, 조건을 만족하는 비트를 결과에 계속 누적합니다.

핵심은 단순히 "특정 비트가 1인 원소의 개수"가 아니라, 지금까지 확정한 패턴(pattern)과 AND 연산을 했을 때 그 패턴이 그대로 유지되는 원소의 개수를 세는 것입니다. 이렇게 해야 이미 선택한 상위 비트들을 보존하면서 새로운 하위 비트를 안전하게 추가할 수 있습니다.

구현 예제

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

// pattern이 유지되는 원소의 개수를 세는 함수
int checkBits(int *arr, int n, int pattern) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if ((pattern & arr[i]) == pattern) {
            ++cnt;
        }
    }
    return cnt;
}

int getMaxBitwiseAnd(int *arr, int n) {
    int result = 0;
    int count;
    // MSB(31)부터 LSB(0)까지 탐욕적으로 비트 결정
    for (int i = 31; i >= 0; --i) {
        count = checkBits(arr, n, result | (1 << i));
        if (count >= 2) {
            result |= (1 << i);
        }
    }
    return result;
}

int main() {
    int arr[] = {10, 12, 15, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum bitwise AND = " << getMaxBitwiseAnd(arr, n) << endl;
    return 0;
}

실행 결과

Maximum bitwise AND = 12

시간 복잡도

checkBits 함수는 배열을 한 번 순회하므로 O(n)이며, 이를 고정된 비트 수(32비트)만큼 반복하므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 추가 배열 없이 O(1)로 처리할 수 있어 매우 효율적인 방법입니다.