C++로 풀어보는 합(Sum)과 XOR이 같은 정수 개수 구하기

문제 개요

이 문제에서는 하나의 정수 n이 주어집니다. 목표는 i = 0부터 n까지의 범위에서 합과 XOR이 같아지는 조건, 즉 (n+i) = (n^i)를 만족하는 정수의 개수를 구하는 프로그램을 작성하는 것입니다.

예제로 문제 이해하기

입력: n = 4

출력: 4

설명:

0부터 n까지의 모든 i 값을 하나씩 확인해 보면 다음과 같습니다.

i = 0 → 4 + 0 = 4, 4 ^ 0 = 4
i = 1 → 4 + 1 = 5, 4 ^ 1 = 5
i = 2 → 4 + 2 = 6, 4 ^ 2 = 6
i = 3 → 4 + 3 = 7, 4 ^ 3 = 7
i = 4 → 4 + 4 = 8, 4 ^ 4 = 0

조건을 만족하는 값은 총 4개이므로 정답은 4입니다.

접근 방법 1: 완전 탐색(Brute Force)

가장 단순한 방법은 n과 i의 합(n+i)과 XOR(n^i)을 각각 계산한 뒤 두 값을 비교하고, 서로 같은 경우의 개수를 세는 것입니다.

알고리즘

1단계: i = 0부터 n까지 반복문을 실행합니다.

1.1단계: (n + i)의 값을 구합니다.

1.2단계: (n ^ i)의 값을 구합니다.

1.3단계: 1.1단계와 1.2단계에서 구한 두 값을 비교합니다.
1.4단계: 두 값이 같으면 카운터를 1 증가시킵니다.

2단계: 최종 count 값을 출력합니다.

구현 예제

#include <iostream>
using namespace std;

int main() {
    int n = 5;
    int counter = 0;
    for(int i=0; i<=n; i++)
        if ( (n+i) == (n^i) )
            counter++;
    cout<<"The count of integers with equal sum and XOR is "<<counter;
    return 0;
}

실행 결과

The count of integers with equal sum and XOR is 2

이 방법도 충분히 유효하지만, 문제의 수학적 성질을 활용하면 더 효율적인 해결책을 만들 수 있습니다.

접근 방법 2: 비트 연산을 활용한 최적화

핵심 아이디어는 다음과 같습니다.

n ^ i = n + i가 성립하려면 반드시 n & i = 0이어야 합니다.

n & i = 0이라는 것은 두 수가 set된 비트의 위치를 서로 공유하지 않아야 한다는 의미입니다. 즉, n의 비트가 1인 자리에는 i의 비트가 반드시 0이어야 하고, n의 비트가 0(unset)인 자리에는 i의 비트가 0 또는 1 어느 쪽이든 될 수 있습니다. 또한 n & i = 0이면 덧셈 과정에서 자리올림(carry)이 발생하지 않기 때문에 합과 XOR의 결과가 항상 동일해집니다.

따라서 n의 unset 비트 개수를 k라고 할 때, 가능한 i의 개수는 2^k가 됩니다. 이 성질을 이용하면 반복문 없이도 답을 바로 계산할 수 있습니다.

구현 예제

#include <iostream>
using namespace std;

int countValuesWithEqualSumXOR(int n) {
    int countUnSetBits=0;
    while (n) {
        if ((n & 1) == 0)
            countUnSetBits++;
        n=n>>1;
    }
    return 1 << countUnSetBits;
}

int main()
{
    int n = 6;
    cout<<"The count of integers with equal sum and XOR is "<<countValuesWithEqualSumXOR(n);
    return 0;
}

실행 결과

The count of integers with equal sum and XOR is 2

마무리

완전 탐색 방식은 O(n)의 시간 복잡도를 가지는 반면, 비트 연산을 활용한 최적화 기법은 n의 비트 길이에 비례하는 O(log n)만에 답을 구할 수 있어 훨씬 효율적입니다. 입력값이 커질 수 있는 상황이라면 후자의 접근 방식을 사용하는 것이 바람직합니다.