정수 num이 주어졌을 때, 먼저 해당 숫자의 이진수(binary) 표현을 구한 뒤 전체 세트 비트(set bit)의 개수를 계산하는 것이 이 글의 목표입니다.
세트 비트란 이진수에서 1로 표현되는 비트를 말합니다. 정수 값을 이진수로 변환하면 0과 1의 조합으로 나타나는데, 컴퓨터 분야에서는 이때의 숫자 1을 '세트 비트'라고 부릅니다.
입력 − int number = 50
출력 − 숫자의 전체 세트 비트 개수: 3
설명 − 숫자 50의 이진 표현은 110010이며, 8자리로 표현하면 앞에 0이 두 개 붙어 00110010이 됩니다. 따라서 전체 세트 비트의 개수는 3개입니다.
입력 − int number = 10
출력 − 숫자의 전체 세트 비트 개수: 2
설명 − 숫자 10의 이진 표현은 1010이며, 8자리로 표현하면 앞에 0이 네 개 붙어 00001010이 됩니다. 따라서 전체 세트 비트의 개수는 2개입니다.
접근 방식
- 정수형 변수에 숫자를 입력받습니다.
- 세트 비트의 총 개수를 저장할
unsigned int타입의 변수 count를 선언합니다. - i를 1 << 7(즉, 128)부터 시작해 i > 0인 동안 i를 절반씩 줄여가며 FOR 반복문을 실행합니다.
- 반복문 안에서
number & i의 결과가 참이면 1을, 거짓이면 0을 출력해 8비트 이진수를 화면에 표시합니다. - 숫자가 0이 아닐 때까지 반복하는 WHILE 반복문으로 전체 세트 비트 개수를 계산합니다.
- 반복문 안에서
count += number & 1로 최하위 비트를 누적하고,number >>= 1로 숫자를 오른쪽으로 한 비트 시프트합니다. - 최종적으로 count 값을 출력합니다.
예제 코드
#include<iostream>
using namespace std;
// 숫자의 전체 세트 비트 개수를 계산하는 함수
unsigned int bits(unsigned int number){
unsigned int count = 0;
unsigned i;
// 8비트 이진수 형태로 출력
cout << "8-bit digits of " << number << " is: ";
for (i = 1 << 7; i > 0; i = i / 2){
(number & i) ? cout << "1" : cout << "0";
}
// 전체 세트 비트 개수 계산
while (number){
count += number & 1;
number >>= 1;
}
cout << "\nCount of total set bits in a number are: " << count;
}
int main(){
int number = 50;
bits(number);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
8-bit digits of 50 is: 00110010 Count of total set bits in a number are: 3
코드 동작 원리
1 << 7은 이진수로 10000000, 즉 십진수 128에 해당하며, 8비트 중 맨 왼쪽 비트만 1인 마스크(mask)입니다. 이 마스크를 number와 AND(&) 연산하면 해당 자리의 비트가 1인지 확인할 수 있습니다. 매 반복마다 i를 절반으로 나누면(오른쪽으로 한 비트 시프트하는 것과 동일) 왼쪽 비트부터 오른쪽까지 차례대로 검사하며 8비트 이진수를 출력할 수 있습니다.
세트 비트 개수 계산도 같은 원리입니다. number & 1로 최하위 비트가 1인지 확인해 count에 더한 뒤, number >>= 1로 오른쪽 시프트를 반복하면 모든 비트를 검사할 수 있습니다. 이 방법의 시간 복잡도는 O(log n)입니다.
더 간편한 대안
GCC나 Clang 컴파일러에서는 내장 함수 __builtin_popcount()를 제공하므로 한 줄로 세트 비트 개수를 구할 수 있습니다. 또한 Brian Kernighan 알고리즘(n &= (n - 1))을 활용하면 세트 비트 개수만큼만 반복하므로 더 효율적인 계산이 가능합니다.
int count = __builtin_popcount(50); // 결과: 3