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

정수 배열이 하나 주어졌을 때, 배열의 값들로 만들 수 있는 모든 쌍 가운데 두 원소에 비트별 XOR(배타적 논리합) 연산을 적용한 결과가 짝수(EVEN)가 되는 쌍의 총 개수를 구하는 것이 이 글의 목표입니다.

XOR 연산의 진리표

XOR 연산은 두 비트가 서로 같으면 0, 다르면 1을 반환합니다. 진리표는 다음과 같습니다.

예제 입력과 출력

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

출력 − XOR 연산 결과가 짝수인 쌍의 개수 − 4

설명 − 배열의 모든 쌍에 대해 XOR 연산을 수행한 결과는 아래와 같으며, 이중 결과가 짝수인 경우는 총 4개입니다.

핵심 아이디어

모든 쌍을 일일이 검사하기 전에 짝수와 홀수의 XOR 성질을 활용하면 문제를 훨씬 간단하게 해결할 수 있습니다.

• 짝수 XOR 짝수 = 짝수
• 홀수 XOR 홀수 = 짝수
• 짝수 XOR 홀수 = 홀수

즉, 전체 쌍의 개수에서 '짝수와 홀수로 이루어진 쌍'의 개수만 빼면 XOR 결과가 짝수인 쌍의 개수를 바로 구할 수 있습니다.

알고리즘 접근 방법

• 쌍을 만들 정수 배열을 입력받습니다.
• 배열의 크기를 계산한 후, 이후 처리를 위해 해당 데이터를 함수로 전달합니다.
• 배열 내 홀수 원소의 개수를 저장할 임시 변수 count를 선언합니다.
• i를 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다.
• 루프 안에서 arr[i] % 2 != 0, 즉 원소가 홀수라면 count를 1 증가시킵니다.
• temp를 size * (size - 1)로 설정하여 전체 순서쌍의 수를 구합니다.
• 또 다른 임시 변수 pairs를 temp / 2로 설정하여 중복을 제거한 전체 쌍의 수를 구합니다.
• 홀수-짝수로 이루어진 쌍의 수를 count * (size - count)로 계산합니다.
• 전체 쌍의 수에서 홀수-짝수 쌍의 수를 빼면 XOR 결과가 짝수인 쌍의 수(even)가 됩니다.
• even 값을 반환하고 결과를 출력합니다.

예제 코드

#include <iostream>
using namespace std;
//비트별 XOR 연산 결과가 짝수인 쌍의 개수를 세는 함수
int XOR_Even(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        if (arr[i] % 2 != 0){
            count++;
        }
    }
    int temp = size * (size-1);
    int Pairs = temp / 2;
    int odd = count * (size - count);
    int even = Pairs - odd;
    return even;
}
int main(){
    int arr[] = { 2, 6, 1, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"비트별 XOR 연산 결과가 짝수인 쌍의 개수는: "<<XOR_Even(arr, size);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

비트별 XOR 연산 결과가 짝수인 쌍의 개수는: 3

복잡도 분석

위 알고리즘은 배열을 단 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 추가적인 자료구조 없이 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 모든 쌍을 직접 검사하는 O(n²) 완전 탐색 방식에 비해 훨씬 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.