C++에서 숫자의 설정되지 않은 비트(Unset Bit)란?
정수 num이 주어졌을 때, 먼저 이 수를 이진수로 변환한 뒤 설정되지 않은 비트(unset bit), 즉 0의 총 개수를 계산하는 것이 목표입니다.
이진수에서 값이 0인 비트를 '설정되지 않은 비트(unset bit)'라고 합니다. 정수를 이진수로 표현하면 0과 1의 조합으로 나타나며, 컴퓨터 관점에서 0에 해당하는 자리가 바로 unset bit입니다.
예제 1
입력 − int number = 50
출력 − 숫자의 총 unset 비트 개수: 5
설명 − 50의 이진 표현은 110010입니다. 이를 8자리로 표현하면 앞에 0이 두 개 추가되어 00110010이 되고, 0은 총 5개이므로 unset 비트는 5개입니다.
예제 2
입력 − int number = 10
출력 − 숫자의 총 unset 비트 개수: 6
설명 − 10의 이진 표현은 00001010이며, 0이 총 6개이므로 unset 비트는 6개입니다.
알고리즘 접근 방법
- 정수형 변수에 숫자를 입력받습니다.
- 설정된 비트(set bit)의 총 개수를 저장할 unsigned int 타입의 count 변수를 선언합니다.
- i를 1 << 7(128)부터 시작해 i > 0을 만족하는 동안 i를 절반씩 줄여 가며 for 루프를 실행합니다.
- 루프 안에서 num & i가 참이면 1을, 거짓이면 0을 출력합니다.
- 루프가 한 번 돌 때마다 숫자의 총 자릿수(total_digits)를 1씩 증가시킵니다.
- 숫자가 0이 아닐 때까지 while 루프를 실행하며 비트를 하나씩 확인합니다.
- 루프 안에서 count += number & 1로 최하위 비트를 누적하고, number >>= 1로 오른쪽 시프트합니다.
- '전체 자릿수 − 설정된 비트 수' 공식으로 unset 비트 개수를 계산합니다.
- 최종 count를 출력합니다.
예제 코드
#include<iostream>
using namespace std;
// 숫자의 총 unset 비트 개수를 세는 함수
unsigned int unset_bits(unsigned int number){
unsigned int total_digits = 0;
unsigned int count = 0;
unsigned int i;
// 8비트 이진수 출력
cout << "8-bit digits of " << number << " is: ";
for (i = 1 << 7; i > 0; i = i / 2){
(number & i) ? cout << "1" : cout << "0";
total_digits++;
}
// 설정된 비트(set bit) 개수 계산
while (number){
count += number & 1;
number >>= 1;
}
// unset 비트 개수 = 전체 자릿수 - set 비트 개수
count = total_digits - count;
cout << "\nCount of total unset bits in a number are: " << count;
}
int main(){
int number = 50;
unset_bits(number);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
8-bit digits of 50 is: 00110010 Count of total unset bits in a number are: 5
동작 원리 정리
핵심 로직은 두 단계로 나뉩니다. 첫 번째 for 루프는 128(1 << 7)부터 시작해 매번 절반씩 나누면서 각 비트 자리를 왼쪽부터 차례로 검사해 8자리 이진수를 출력하고, 동시에 전체 자릿수를 셉니다. 두 번째 while 루프는 number가 0이 될 때까지 최하위 비트(number & 1)를 확인해 설정된 비트의 개수만 누적합니다. 마지막으로 전체 자릿수에서 설정된 비트 수를 빼면 곧 unset 비트(0)의 개수가 됩니다.
이 방식의 시간 복잡도는 O(log n)이며, 8비트처럼 폭이 고정된 경우에는 상수 시간에 처리됩니다. 1 << 7의 시프트 값을 조정하면 16비트, 32비트 등 다른 폭의 이진 표현에도 손쉽게 확장할 수 있습니다.