문제 소개
하나의 정수 num이 주어졌을 때, num보다 작은 수들 중에서 num과 XOR(배타적 논리합) 연산을 수행한 결과가 num 자신보다 큰 값이 되는 숫자의 개수를 구하는 것이 이 글의 목표입니다.
XOR 연산의 진리표
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
입력/출력 예제
입력 − int num = 11
출력 − n과 XOR 연산 결과가 더 큰 값이 되는 더 작은 숫자의 개수 − 4
설명 −
num이 11로 주어졌으므로, 11보다 작은 모든 수와 11의 XOR 결과를 하나씩 확인해야 합니다. 1 XOR 11 = 10 < 11(거짓), 2 XOR 11 = 9 < 11(거짓), 3 XOR 11 = 8 < 11(거짓), 4 XOR 11 = 15 > 11(참), 5 XOR 11 = 14 > 11(참), 6 XOR 11 = 13 > 11(참), 7 XOR 11 = 12 > 11(참), 8 XOR 11 = 3 < 11(거짓), 9 XOR 11 = 2 < 11(거짓), 10 XOR 11 = 1 < 11(거짓). 따라서 조건을 만족하는 수는 총 4개입니다.
입력 − int num = 12
출력 − n과 XOR 연산 결과가 더 큰 값이 되는 더 작은 숫자의 개수 − 3
설명 −
num이 12로 주어졌을 때, 12보다 작은 수들의 XOR 결과를 살펴보면 1 XOR 12 = 13 > 12(참), 2 XOR 12 = 14 > 12(참), 3 XOR 12 = 15 > 12(참)이고, 4부터 11까지의 나머지 수들은 모두 XOR 결과가 12보다 작습니다(거짓). 따라서 조건을 만족하는 수는 총 3개입니다.
핵심 아이디어
x XOR n의 결과가 n보다 커지려면, x의 최상위 설정 비트(가장 왼쪽에 있는 1비트)가 위치한 자리에서 n의 비트가 반드시 0이어야 합니다. 그보다 위의 자리에서는 두 수의 비트가 같아야 하며(그렇지 않으면 x가 n 이상이 됩니다), 처음으로 달라지는 자리에서 n이 0이고 x가 1이면 XOR 결과가 그 자리에서 1이 되어 n보다 커지게 됩니다.
따라서 정답은 n의 이진 표현에서 0인 각 비트 자리 p에 대해 2p를 모두 더한 값과 같습니다.
알고리즘 접근 방식
- 정수를 입력받아 변수 num에 저장합니다.
- num 값을 처리용 함수에 전달합니다.
- 결과를 저장할 임시 변수 count를 선언하고 0으로 초기화합니다.
- num > 0인 동안 WHILE 루프를 실행합니다.
- 루프 내부에서 현재 최하위 비트가 0인지 검사하고, 0이라면 count에 2temp(pow(2, temp))를 더합니다.
- temp 값을 1 증가시킵니다.
- num을 오른쪽으로 한 비트 시프트합니다(num >>= 1).
- 루프가 종료되면 count를 반환합니다.
- 결과를 출력합니다.
C++ 구현 예제
#include <iostream>
#include <cmath>
using namespace std;
// n과 XOR 연산 시 더 큰 값이 되는 더 작은 숫자의 개수를 세는 함수
int XOR_greater(int n){
int temp = 0;
int count = 0;
while (n > 0){
if ((n & 1) == 0){
count += pow(2, temp);
}
temp++;
n >>= 1;
}
return count;
}
int main(){
int n = 20;
cout << "n과 XOR 연산 시 더 큰 값이 되는 더 작은 숫자의 개수: " << XOR_greater(n) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
n과 XOR 연산 시 더 큰 값이 되는 더 작은 숫자의 개수: 11
복잡도 분석
이 알고리즘은 n의 비트 수에 비례하여 동작하므로 시간 복잡도는 O(log n)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 1부터 n-1까지 모든 수에 대해 XOR을 일일이 계산하는 O(n)의 단순 무차별 대입 방식보다 훨씬 효율적입니다.