C++에서 X와의 합이 X와의 XOR과 같은 숫자 개수 구하기

하나의 정수 X가 주어졌을 때, 0부터 X 사이에 있는 숫자 중에서 X와의 합(Sum)이 X와의 XOR(배타적 논리합) 결과와 동일한 숫자의 개수를 구하는 것이 목표입니다.

가장 직관적인 방법은 i=0부터 i<=X까지 모든 숫자를 하나씩 확인하면서, 각 i에 대해 조건식 (i+X==i^X)이 참이면 카운트를 1씩 증가시키는 것입니다.

예시를 통해 좀 더 쉽게 이해해 보겠습니다.

입력 − X=6

출력 − X와의 합이 X와의 XOR과 같은 숫자의 개수: 2

설명 − 조건을 만족하는 숫자는 0과 1뿐입니다.

입력 − X=20

출력 − X와의 합이 X와의 XOR과 같은 숫자의 개수: 8

설명 − 조건을 만족하는 숫자는 0, 1, 2, 3, 8, 9, 10, 11입니다.

프로그램에 적용된 접근 방식

• 정수 X를 입력받습니다.

• sumisXOR(int x) 함수는 x를 인자로 받아, x와의 합이 x와의 XOR과 같은 숫자의 개수를 반환합니다.

• 카운트 변수를 0으로 초기화합니다.

• i=0부터 i<=x까지 반복문을 실행합니다.

• i+x == i^x 조건이 참이면 카운트를 증가시킵니다.

• 반복문이 종료되면 count에는 원하는 결과가 저장되어 있습니다.

• count를 반환하여 출력합니다.

조건이 성립하는 수학적 원리

i + X == i ^ X가 성립하려면 두 수를 더할 때 자리올림(carry)이 전혀 발생하지 않아야 합니다. 이진수 덧셈에서 자리올림은 같은 자리의 두 비트가 모두 1일 때 발생하므로, 이 조건은 곧 (i & X) == 0, 즉 i와 X가 비트 단위로 서로 겹치지 않는다는 의미와 같습니다. 예를 들어 X=6(이진수 110)이라면, i는 0(000) 또는 1(001)만 가능합니다.

예제 코드

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int sumisXOR(int x){
    int count = 0;
    for (int i = 0; i <= x; i++){
        if((i+x)==(i^x))
            { count++; }
    }
    return count;
}
int main(){
    int X = 15;
    int nums=sumisXOR(X);
    cout <<endl<<"X와의 합이 X와의 XOR과 같은 숫자의 개수: "<<nums;
    return 0;
}

실행 결과

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

X와의 합이 X와의 XOR과 같은 숫자의 개수: 1