C++에서 N과 XOR한 값이 N과 OR한 값과 같은 숫자 개수 세기

문제 개요

숫자 N이 주어졌을 때, 0부터 N 사이의 숫자 중 N과 OR 연산을 한 결과가 N과 XOR 연산을 한 결과와 같은 숫자의 개수를 구하는 것이 목표입니다.

구현 방법은 간단합니다. i=0부터 i<=N까지 모든 숫자를 순회하면서, 각 i에 대해 (N^i == i|N) 조건을 만족하는 경우 카운트를 1씩 증가시키면 됩니다.

예시를 통해 자세히 살펴보겠습니다.

입력 − X=6

출력 − N과 OR한 값이 XOR한 값과 같은 숫자의 개수: 2

설명 − 해당하는 숫자는 0, 1입니다.

입력 − X=20

출력 − N과 OR한 값이 XOR한 값과 같은 숫자의 개수: 8

설명 − 해당하는 숫자는 0, 1, 2, 3, 8, 9, 10, 11입니다.

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

• 정수 N을 입력받습니다.

• 함수 orisXOR(int n)은 n을 매개변수로 받아, n과 OR 연산한 값이 XOR 연산한 값과 같은 숫자의 개수를 반환합니다.

• 초기 카운트 값을 0으로 설정합니다.

• i=0부터 i<=n까지 반복문을 순회합니다.

• 만약 i|n == i^n 조건을 만족하면 카운트를 증가시킵니다.

• for 루프가 종료되면 count 변수에 원하는 결과가 저장됩니다.

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

동작 원리

OR 연산과 XOR 연산의 차이는 두 비트가 모두 1일 때 발생합니다. OR은 1을 반환하지만 XOR은 0을 반환하기 때문입니다. 따라서 i|n == i^n이 성립하려면 i와 n이 공통으로 1을 가지는 비트 자리가 없어야 하며, 이는 곧 (i & n) == 0과 동치입니다.

예제 코드

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int orisXOR(int n){
    int count = 0;
    for (int i = 0; i <= n; i++){
        if((n|i)==(i^n))
            { count++; }
    }
    return count;
}
int main(){
    int N = 15;
    int nums=orisXOR(N);
    cout <<endl<<"Count of numbers whose OR with N == XOR with N: "<<nums;
    return 0;
}

실행 결과

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

Count of numbers whose OR with N == XOR with N: 1

N=15는 이진수로 1111이므로 모든 비트가 1입니다. 따라서 N과 비트가 겹치지 않는 숫자는 0 하나뿐이며, 결과값 1이 정확히 일치함을 확인할 수 있습니다.