C++로 n = x + (n XOR x) 방정식의 해 개수 구하기

이 글에서는 n = x + (n ⊕ x) 방정식의 해의 개수를 구하는 방법을 다룹니다. 즉, 주어진 값 n에 대해 이 방정식을 만족하는 x 값이 몇 가지 존재하는지 찾는 것이며, 여기서 ⊕는 XOR(배타적 논리합) 연산을 의미합니다.

지금부터 브루트 포스(Brute Force) 방법과 비트 연산을 활용한 효율적인 접근 방식, 두 가지 방법을 예제와 함께 자세히 살펴보겠습니다.

브루트 포스 방법

가장 단순한 방법은 가능한 모든 경우를 하나씩 시도해 보는 것입니다. 주어진 n에 대해 x를 0부터 시작하여 정숫값을 차례대로 대입하고, 각 경우에 방정식이 성립하는지 확인합니다. 이때 x의 범위는 0부터 n까지입니다. x가 n보다 커지면 (n ⊕ x)를 더한 결과가 절대 n이 될 수 없기 때문입니다.

예제

n = 3일 때 해가 되는 x 값을 하나 찾아보겠습니다.

    n = x + (n ⊕ x)
x = 0을 대입하면,
    3 = 0 + (3 ⊕ 0)
3 ⊕ 0 = 3 이므로,
    3 = 3
LHS = RHS → x = 0은 방정식을 만족
따라서 x = 0은 해 중 하나입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 3, c = 0;
    // x 값을 0부터 n까지 순차적으로 대입
    for (int x = 0; x <= n; ++x)
        if (n == (x + (n ^ x))) // x가 방정식을 만족하는지 검사
            ++c;
    cout << "가능한 해의 개수 : " << c;
    return 0;
}

출력 결과

가능한 해의 개수 : 4

위 프로그램은 브루트 포스 방식으로 n = x + (n ⊕ x)의 해의 개수를 구하는 간단한 C++ 코드입니다. 참고로, C++에서 XOR 연산자(^)는 덧셈보다 우선순위가 낮으므로 괄호를 사용하여 의도한 대로 연산 순서를 명확히 지정해야 합니다.

효율적인 접근 방식

더 효율적으로 문제를 해결하려면 n을 이진수로 표현했을 때 1로 설정된 비트(set bit)의 개수에 주목해야 합니다. 방정식을 분석해 보면, n의 특정 비트가 1로 설정되어 있다면 x 또는 (n ⊕ x) 중 정확히 하나만 해당 비트가 1이 될 수 있습니다. 1 ⊕ 1 = 0이므로 두 값이 같은 비트를 동시에 가질 수 없기 때문입니다. 따라서 n의 설정된 비트 하나하나마다 두 가지 선택지가 존재하게 되고, 전체 해의 개수는 2^(설정된 비트의 개수)가 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int main (){
    int n = 3, no_of_setbits = 0; // n 초기화 및 설정 비트 카운트 변수 선언
    while (n != 0){
        no_of_setbits += (n % 2); // 최하위 비트가 1인지 확인
        n = n / 2;
    }
    int result = 1 << no_of_setbits; // 2^setbits로 해의 개수 계산
    cout << "가능한 해의 개수 : " << result;
    return 0;
}

출력 결과

가능한 해의 개수 : 4

n = 3은 이진수로 11이므로 설정된 비트가 2개이고, 2² = 4가 곧 해의 개수가 됩니다. 브루트 포스 결과와 일치하는 것을 확인할 수 있습니다.

시간 복잡도

브루트 포스 방법은 x를 0부터 n까지 모두 검사하므로 시간 복잡도는 O(n)입니다. 반면, 설정된 비트의 개수를 세는 효율적인 방법은 n을 반복적으로 2로 나누므로 시간 복잡도가 O(log n)으로 훨씬 빠릅니다. n이 큰 경우에는 후자의 방법을 사용하는 것이 바람직합니다.

결론

이 글에서는 n = x + (n ⊕ x) 방정식의 해의 개수를 구하는 문제를 다루었습니다. 모든 경우를 시도하는 브루트 포스 방법과, 이진수의 설정된 비트 개수를 활용해 2^(설정 비트 수)로 답을 구하는 효율적인 방법을 학습했으며, 각각의 C++ 구현 코드와 함께 문제 해결 과정을 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 도움이 되기를 바랍니다.