C++에서 XOR 연산자 없이 두 숫자의 XOR 구하는 방법

이 문제에서는 두 개의 정수 A와 B가 주어지며, XOR 연산자(^)를 사용하지 않고 두 숫자의 XOR 값을 구하는 것이 과제입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력 : A = 4, B = 5
출력 : 1

풀이 접근 방법 1: 비트 단위 연산 활용

이 문제를 해결하는 한 가지 방법은 두 숫자를 각각의 이진수로 변환한 뒤, 아래 진리표(truth table)를 기준으로 비트 단위 연산을 수행하는 것입니다.

XOR의 특성상 두 비트가 서로 다를 때만 결과가 1이 됩니다. 위 표를 코드로 구현하면 다음과 같습니다.

예제 코드

아래 프로그램은 이 풀이가 실제로 동작하는 모습을 보여줍니다.

#include <iostream>
using namespace std;

int calcXORwoOperator(int a, int b){
    int xorVal = 0;
    for (int i = 31; i >= 0; i--){
        bool val1 = a & (1 << i);
        bool val2 = b & (1 << i);
        bool xorBit = (val1 & val2) ? 0 : (val1 | val2);
        xorVal <<= 1;
        xorVal |= xorBit;
    }
    return xorVal;
}

int main(){
    int a = 4, b = 5;
    cout<<"두 숫자의 XOR 값은 "<<calcXORwoOperator(a, b);
   return 0;
}

출력 결과

두 숫자의 XOR 값은 1

이 코드는 각 비트 자리를 왼쪽부터 오른쪽까지 검사하면서, 두 비트가 모두 1인 경우에는 0을, 그 외에는 OR 연산의 결과를 저장하여 최종 XOR 값을 만들어냅니다.

풀이 접근 방법 2: 산술식을 이용한 대안

XOR을 구하는 또 다른 우아한 방법은 두 숫자의 비트를 하나씩 비교하는 대신, 수학적 등가 관계를 활용하는 것입니다.

다음 식은 XOR 연산과 정확히 같은 결과를 반환합니다.

(a | b) - (a & b)

그 이유는 다음과 같습니다. (a | b)는 두 숫자 중 하나라도 1인 비트를 모두 포함하고, (a & b)는 양쪽 모두 1인 비트만 포함합니다. 따라서 OR 결과에서 AND 결과를 빼면, 두 비트가 서로 다른 자리만 남게 되는데, 이것이 바로 XOR의 정의입니다.

예제 코드

#include <iostream>
#include <bitset>
using namespace std;

int calcXORwoOperator(int a, int b) {
   return (a | b) - (a & b);
}

int main(){
   int a = 4;
   int b = 5;
   cout<<"두 숫자의 XOR 값은 "<<(bitset<8>(calcXORwoOperator(a, b)));
   return 0;
}

출력 결과

두 숫자의 XOR 값은 00000001

두 번째 방법은 반복문 없이 단 한 줄의 연산으로 XOR을 계산할 수 있어 더 간결하고 효율적이라는 장점이 있습니다. 실무에서도 일반적으로 이 산술식 기반 접근법이 선호됩니다.