하나의 숫자가 주어졌을 때, 0부터 해당 숫자(num)까지의 범위 내에서 세트 비트(set bit)가 정확히 하나만 있는 숫자의 개수를 구하는 것이 이번 글의 목표입니다.
이진수에서 세트 비트란 값이 1인 비트를 의미합니다. 정수를 이진수로 변환하면 0과 1의 조합으로 표현되는데, 이때의 1이 바로 컴퓨터 용어에서 말하는 '세트 비트'입니다.
예시 1
입력: int num = 15
출력: [0, 15] 범위에서 세트 비트가 1개뿐인 숫자의 개수 − 4
설명: 주어진 숫자가 15이므로 탐색 범위는 0부터 15까지입니다. 각 숫자를 4자리 이진수로 나타내면 다음과 같습니다.
0 → 0000 = 세트 비트 0개, 1 → 0001 = 세트 비트 1개, 2 → 0010 = 세트 비트 1개, 3 → 0011 = 세트 비트 2개, 4 → 0100 = 세트 비트 1개, 5 → 0101 = 세트 비트 2개, 6 → 0110 = 세트 비트 2개, 7 → 0111 = 세트 비트 3개, 8 → 1000 = 세트 비트 1개, 9 → 1001 = 세트 비트 2개, 10 → 1010 = 세트 비트 2개, 11 → 1011 = 세트 비트 3개, 12 → 1100 = 세트 비트 2개, 13 → 1101 = 세트 비트 3개, 14 → 1110 = 세트 비트 3개, 15 → 1111 = 세트 비트 4개.
따라서 세트 비트가 정확히 하나인 숫자는 1, 2, 4, 8로 총 4개입니다.
예시 2
입력: int num = 4
출력: [0, 4] 범위에서 세트 비트가 1개뿐인 숫자의 개수 − 3
설명: 주어진 숫자가 4이므로 탐색 범위는 0부터 4까지입니다. 각 숫자를 이진수로 나타내면 0 → 0000(0개), 1 → 0001(1개), 2 → 0010(1개), 3 → 0011(2개), 4 → 0100(1개)이므로, 조건을 만족하는 숫자는 1, 2, 4로 총 3개입니다.
접근법 1: 단순 반복 (Naive Approach)
가장 직관적인 방법은 범위 내 모든 숫자를 하나씩 검사하는 것입니다.
- 숫자를 입력받아 처리용 함수에 전달합니다.
- 세트 비트가 정확히 1개인 숫자의 개수를 저장할 변수 count를 준비합니다.
- i를 1부터 주어진 숫자까지 반복하는 for 루프를 실행합니다.
- 루프 안에서
__builtin_popcount(i)함수를 호출해 i의 세트 비트 개수를 구합니다. 이 함수는 비트가 1인 자릿수를 반환합니다. - 세트 비트 개수가 1이면 count를 증가시킵니다.
- 루프 종료 후 count를 반환하고 결과를 출력합니다.
예제 코드 (단순 반복)
#include <iostream>
using namespace std;
// [0, n] 범위에서 세트 비트가 1개뿐인 숫자의 개수를 구하는 함수
int set_bits(int number){
int count = 0;
for (int i = 1; i <= number; i++){
int temp = __builtin_popcount(i);
if (temp == 1){
count++;
}
}
return count;
}
int main(){
int number = 15;
cout<<"[0, "<<number<<"] 범위에서 세트 비트가 1개뿐인 숫자의 개수: "<<set_bits(number);
return 0;
}
실행 결과
[0, 15] 범위에서 세트 비트가 1개뿐인 숫자의 개수: 4
접근법 2: 효율적 방법 (Efficient Approach)
사실 세트 비트가 정확히 하나뿐인 숫자는 곧 2의 거듭제곱, 즉 1, 2, 4, 8, 16, ... 입니다. 이 성질을 이용하면 모든 숫자를 일일이 검사할 필요 없이, 주어진 범위 이하의 2의 거듭제곱 개수만 세면 됩니다. 시간 복잡도가 O(n)에서 O(log n)으로 크게 향상됩니다.
- 숫자를 입력받아 처리용 함수에 전달합니다.
- 개수를 저장할 변수 count와, 초기값이 1인 변수 temp를 준비합니다.
- temp가 number보다 작거나 같은 동안 while 루프를 반복합니다.
- 루프 안에서 count를 1 증가시키고, temp를 temp × 2로 갱신합니다.
- 루프 종료 후 count를 반환하고 결과를 출력합니다.
예제 코드 (효율적 방법)
#include <iostream>
using namespace std;
// [0, n] 범위에서 세트 비트가 1개뿐인 숫자의 개수를 구하는 함수
int set_bits(int number){
int count = 0;
int temp = 1;
while(temp <= number){
count++;
temp = temp * 2;
}
return count;
}
int main(){
int number = 15;
cout<<"[0, "<<number<<"] 범위에서 세트 비트가 1개뿐인 숫자의 개수: "<<set_bits(number);
return 0;
}
실행 결과
[0, 15] 범위에서 세트 비트가 1개뿐인 숫자의 개수: 4
정리
두 접근법 모두 동일한 결과를 반환하지만, 단순 반복 방식은 범위 내 모든 숫자에 대해 popcount 연산을 수행해야 하는 반면, 효율적 방식은 '세트 비트가 하나뿐인 수 = 2의 거듭제곱'이라는 수학적 성질을 활용해 로그 시간 안에 답을 구할 수 있습니다. 입력 크기가 클수록 효율적 방법의 장점이 극대화됩니다.