C++로 배열 내 모든 쌍의 XOR 합계 구하는 방법

이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어지며, 배열에 있는 모든 쌍(pair)의 XOR 연산 결과를 합산한 값을 구하는 프로그램을 만드는 것이 목표입니다.

문제 이해를 위한 예시

입력: arr[] = {5, 1, 4}
출력: 10
설명: 모든 쌍의 XOR 값은 다음과 같습니다.
5 ^ 1 = 4
1 ^ 4 = 5
5 ^ 4 = 1
합계 = 4 + 5 + 1 = 10

방법 1: 중첩 반복문을 이용한 단순 접근

가장 간단한 해결 방법은 중첩 반복문을 사용하여 배열의 모든 숫자 쌍을 찾는 것입니다. 각 쌍의 XOR 값을 계산하고, 그 결과를 합계에 더하면 됩니다.

알고리즘

sum = 0으로 초기화
1단계: for(i -> 0부터 n까지) 반복:
    1.1단계: for(j -> i부터 n까지) 반복:
        1.1.1단계: sum 갱신 → sum += arr[i] ^ arr[j]
2단계: sum 반환

구현 예제

아래는 위 알고리즘의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int findXORSum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            sum += (arr[i]^arr[j]);
    return sum;
}
int main() {
    int arr[] = { 5, 1, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"배열의 모든 쌍의 XOR 합계: "<<findXORSum(arr, n);
    return 0;
}

실행 결과

배열의 모든 쌍의 XOR 합계: 10

이 알고리즘의 시간 복잡도는 O(n²)이므로, 배열의 크기가 커질수록 비효율적이라는 한계가 있습니다.

방법 2: 비트 조작 기법을 활용한 효율적인 접근

더 효율적인 해결 방법은 비트 조작(bit manipulation) 기법을 활용하는 것입니다.

핵심 아이디어는 각 비트 위치별로 배열의 모든 숫자를 살펴보는 것입니다. 특정 비트 위치에서 XOR 결과가 1이 되려면 두 숫자 중 하나는 해당 비트가 1(set bit), 다른 하나는 0(unset bit)이어야 합니다. 따라서 각 비트 위치에서의 부분 합은 다음 공식으로 계산할 수 있습니다.

(set bit 개수) × (unset bit 개수) × (2^비트_위치)

최종 합계는 모든 비트 위치에서 계산된 부분 합들을 모두 더하여 구합니다.

알고리즘

sum = 0, setBits = 0, unsetBits = 0으로 초기화
1단계: i -> 0부터 31(또는 64)까지 반복하며 2~4단계 수행
2단계: setBits와 unsetBits를 0으로 초기화
3단계: 배열의 각 원소에 대해 i번째 비트 위치의 set/unset 여부를 확인하여 카운트
4단계: sum += (setBits * unsetBits * (2^i)) 갱신

구현 예제

아래는 효율적인 접근 방식의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
#include <math.h>
using namespace std;
long findXORSum(int arr[], int n) {
    long sum = 0;
    int unsetBits = 0, setBits = 0;
    for (int i = 0; i < 32; i++) {
        unsetBits = 0; setBits = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] % 2 == 0)
                unsetBits++;
            else
                setBits++;
            arr[j] /= 2;
        }
        sum += ( unsetBits*setBits* (pow(2,i)) );
    }
    return sum;
}
int main() {
    int arr[] = { 5, 1, 4, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"배열의 모든 쌍의 XOR 합계: "<<findXORSum(arr, n);
    return 0;
}

실행 결과

배열의 모든 쌍의 XOR 합계: 68

두 방법의 비교

비트 조작 기법을 사용한 방법의 시간 복잡도는 O(n × b)입니다. 여기서 b는 정수의 비트 수(예: 32 또는 64)를 의미합니다. 일반적으로 b는 상수로 취급되므로 사실상 선형 시간인 O(n)에 가깝게 동작하며, 중첩 반복문을 사용하는 O(n²) 방식보다 훨씬 효율적입니다.