C++에서 비트 AND 연산 결과가 짝수가 되는 쌍의 개수 구하기

정수 배열이 하나 주어지며, 이 배열의 값들을 이용해 만들 수 있는 모든 쌍(pair) 가운데 두 값의 비트 AND 연산 결과가 짝수가 되는 쌍의 총개수를 구하는 것이 목표입니다.

AND 연산의 진리표

비트 AND 연산은 두 비트가 모두 1일 때만 1을 반환하고, 그 외의 경우에는 0을 반환합니다.

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

출력 − AND 결과가 짝수인 쌍의 개수: 7

결과 검증

배열 {2, 5, 1, 8, 9}로 만들 수 있는 모든 쌍의 AND 연산 결과는 다음과 같습니다.

총 10개의 쌍 중 AND 결과가 짝수인 경우는 7개입니다. 나머지 3개(5&1, 5&9, 1&9)는 결과가 홀수인데, 공통점은 두 수가 모두 홀수라는 점입니다.

핵심 아이디어와 접근 방법

AND 연산의 성질을 살펴보면, 결과가 홀수가 되려면 두 수의 최하위 비트(LSB)가 모두 1이어야 합니다. 다시 말해 두 수가 모두 홀수일 때만 AND 결과가 홀수가 되고, 쌍 중 하나라도 짝수가 포함되면 결과는 반드시 짝수입니다.

따라서 모든 쌍을 일일이 확인하는 O(n²) 브루트포스 대신, 배열을 한 번만 순회해 홀수의 개수만 세면 O(n) 만에 답을 구할 수 있습니다.

• 정수 배열을 입력받고, 배열 크기를 계산해 처리 함수에 전달합니다.
• 배열을 한 번 순회하며 홀수 원소의 개수를 변수 count에 저장합니다.
• 홀수끼리 만들 수 있는 쌍의 수는 조합 공식에 따라 count × (count − 1) / 2 입니다. 이 쌍들이 유일하게 AND 결과가 홀수가 되는 경우입니다.
• 전체 쌍의 개수는 size × (size − 1) / 2 로 계산합니다.
• 전체 쌍의 수에서 홀수 결과 쌍의 수를 빼면, AND 결과가 짝수인 쌍의 개수가 됩니다.
• 최종 결과를 반환한 뒤 출력합니다.

예제 코드(C++)

#include <iostream>
using namespace std;

// 비트 AND 결과가 짝수인 쌍의 개수를 구하는 함수
int count_pair(int arr[], int size){
    int count = 0;
    // 홀수 원소의 개수를 셉니다
    for (int i = 0; i < size; i++){
        if (arr[i] % 2 != 0){
            count++;
        }
    }
    // 두 수 모두 홀수인 쌍의 개수 (AND 결과가 홀수인 쌍)
    int odd_pairs = count * (count - 1) / 2;
    // 전체 쌍의 개수
    int total_pair = size * (size - 1) / 2;
    // 전체 쌍에서 홀수 결과 쌍을 빼면 짝수 결과 쌍의 개수
    return total_pair - odd_pairs;
}

int main(){
    int arr[] = {2, 5, 1, 8, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"비트 AND 결과가 짝수인 쌍의 개수: "<<count_pair(arr, size) << endl;
    return 0;
}

실행 결과

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

비트 AND 결과가 짝수인 쌍의 개수: 7

예제 배열 {2, 5, 1, 8, 3}에는 홀수가 3개(5, 1, 3) 있으므로, 홀수 결과 쌍은 3 × 2 / 2 = 3개입니다. 전체 쌍 10개에서 3개를 빼면 7개가 되어 실행 결과와 일치합니다.

복잡도 분석

• 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
• 공간 복잡도: O(1) — 추가 메모리를 거의 사용하지 않습니다.