개요
정수 num과 왼쪽(left), 오른쪽(right) 값으로 정의된 범위가 주어졌을 때, 먼저 숫자의 이진수 표현을 구한 뒤 왼쪽 비트부터 오른쪽 비트까지 차례대로 검사하면서 해당 범위 안에 있는 세트 비트의 개수를 계산하는 것이 목표입니다.
이진수에서 세트 비트(set bit)란 값이 1인 비트를 의미합니다. 정수를 이진수로 변환하면 0과 1의 조합으로 표현되는데, 컴퓨터 공학에서는 값이 1인 비트를 '세트 비트'라고 부릅니다.
입출력 예시
입력 − int number = 50, left = 2, right = 5
출력 − 범위 내 총 세트 비트 개수: 2
설명: 50의 이진수 표현은 110010입니다. left = 2 위치부터 right = 5 위치까지의 범위에서 양쪽 끝에 세트 비트(1)가 하나씩 존재하고 그 사이는 모두 0이므로, 세트 비트의 개수는 2가 됩니다.
입력 − int number = 42, left = 3, right = 4
출력 − 범위 내 총 세트 비트 개수: 1
설명: 42의 이진수 표현은 101010입니다. left = 3부터 right = 4까지의 범위 안에는 세트 비트가 단 하나만 포함되어 있으므로 결과는 1입니다.
프로그램에서 사용하는 접근 방식
- 정수형 변수에 숫자를 입력받고, 왼쪽과 오른쪽 경계값도 함께 저장합니다.
- 세트 비트의 총 개수를 저장할 unsigned int 타입의 count 변수를 선언합니다.
- i를 1 << 7부터 시작해서 i > 0을 만족하는 동안 i를 i / 2로 줄여가며 FOR 반복문을 실행합니다.
- 반복문 안에서 num & i가 참(TRUE)이면 1을, 거짓이면 0을 출력하여 8비트 이진수 전체를 화면에 표시합니다.
- 숫자가 0이 될 때까지 while 반복문을 실행하며 전체 비트 개수를 계산합니다.
- 반복문 안에서 count += number & 1로 최하위 비트를 더하고, number >>= 1로 숫자를 오른쪽으로 한 비트씩 시프트합니다.
- 임시 변수 a에 ((1 << right) - 1) ^ ((1 << (left - 1)) - 1) 식으로 계산되는 비트 마스크를 대입합니다.
- count를 count & a로 갱신하여 지정된 범위 내의 세트 비트만 남깁니다.
- 최종적으로 count 값을 출력합니다.
예제 코드
#include<iostream>
using namespace std;
//범위 내 총 비트 개수 계산
unsigned int bits(unsigned int number, unsigned int left, unsigned int right){
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;
}
//범위 내 세트 비트 계산
int a = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);
count = count & a;
cout<<"\nCount of total set bits in a range are: "<<count;
}
int main(){
unsigned int number = 42;
unsigned int left = 2, right = 5;
bits(number, left, right);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
8-bit digits of 42 is: 00101010 Count of total set bits in a range are: 2