C++로 비트 OR 연산 결과가 쌍의 최댓값 이하인 쌍의 개수 세기

정수 배열이 하나 주어지며, 배열의 값들로 만들 수 있는 모든 쌍(pair) 가운데 두 원소에 비트 OR 연산을 적용한 결과가 그 쌍의 최댓값(MAX)보다 작거나 같은 쌍의 총 개수를 세는 것이 이 글의 목표입니다.

OR 연산의 진리표

입력 − int arr[] = {2, 5, 1, 8, 9}

출력 − 비트 OR 결과가 최댓값 이하인 쌍의 개수 − 3

설명 − 아래 표는 배열 {2, 5, 1, 8, 9}에서 만들 수 있는 모든 쌍과 각각의 OR 연산 결과를 나타낸 것입니다. 조건을 만족하는 쌍은 (5, 1), (1, 9), (8, 9)로 총 3개입니다.

프로그램에서 사용된 접근 방식

• 쌍을 만들 정수 배열을 입력받습니다.
• 배열의 크기를 계산한 뒤, 이후 처리를 위해 데이터를 함수에 전달합니다.
• 쌍의 최댓값보다 작거나 같은 OR 연산 결과를 가진 쌍의 개수를 저장할 임시 변수 count를 생성합니다.
• i를 0부터 배열 크기 − 1까지 순회하는 FOR 루프를 시작합니다.
• 루프 내부에서 j를 i + 1부터 배열 크기까지 순회하는 또 다른 FOR 루프를 시작합니다.
• 루프 내부에서 arr[i] | arr[j]의 값이 max(arr[i], arr[j])보다 작거나 같은지 검사하고, 참이면 count를 1 증가시킵니다.
• 모든 탐색이 끝나면 count를 반환합니다.
• 결과를 화면에 출력합니다.

참고: 조건이 성립하는 경우의 특징

x ∨ y의 결과가 두 값 중 큰 값과 같아지려면, 작은 값의 모든 비트가 큰 값의 비트 안에 포함되어 있어야 합니다. 예를 들어 5(101₂)와 1(001₂)의 OR은 101₂, 즉 5가 되어 조건을 만족하지만, 2(010₂)와 5(101₂)의 OR은 111₂, 즉 7이 되어 최댓값인 5보다 커집니다. 다시 말해, 한 수가 다른 수의 '비트 부분 집합'일 때만 이 조건이 성립합니다. 위 알고리즘의 시간 복잡도는 모든 쌍을 검사하므로 O(n²)입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
//비트 OR 결과가 최댓값 이하인 쌍의 개수 세기
int Pair_OR(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size - 1; i++){
        for (int j = i + 1; j < size; j++){
            if ((arr[i] | arr[j]) <= max(arr[i], arr[j])){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 4, 8, 9, 10, 23};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"비트 OR 결과가 최댓값 이하인 쌍의 개수: "<<Pair_OR(arr, size);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

비트 OR 결과가 최댓값 이하인 쌍의 개수 − 3