이 문제에서는 하나의 숫자가 주어지며, 우리의 과제는 해당 숫자의 이진 표현에 포함된 0과 1의 개수를 각각 세어 두 개수의 XOR 값을 구하는 것입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
n = 9
출력
0
설명
이진수 = 1001 0의 개수 = 2 1의 개수 = 2 2 ^ 2 = 0
이 문제를 해결하기 위해서는 먼저 숫자를 이진수로 변환한 뒤, 각 비트를 하나씩 확인하며 0과 1의 개수를 카운트하고, 마지막으로 두 개수의 XOR 연산을 수행하면 됩니다.
위에서 설명한 해결 방법을 구현한 프로그램입니다.
예제
#include<iostream>
using namespace std;
int countXOR10(int n) {
int count0s = 0, count1s = 0;
while (n){
(n % 2 == 0) ? count0s++ :count1s++;
n /= 2;
}
return (count0s ^ count1s);
}
int main() {
int n = 21;
cout<<"숫자 "<<n<<"의 이진 표현에서 0과 1 개수의 XOR 값은 "<<countXOR10(n);
return 0;
}출력
숫자 21의 이진 표현에서 0과 1 개수의 XOR 값은 1
결과가 1이 나오는 이유는 다음과 같습니다. 숫자 21을 이진수로 표현하면 10101이 되는데, 여기에는 0이 2개, 1이 3개 포함되어 있습니다. 따라서 2 ^ 3 = 1이 되어 최종 결과값으로 1이 출력됩니다.
이 알고리즘은 숫자의 모든 비트를 한 번씩만 확인하면 되기 때문에 시간 복잡도는 O(log n)이며, 추가적인 저장 공간 없이 두 개의 카운터 변수만 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다.