정수 num과 왼쪽(left), 오른쪽(right) 값으로 구성된 범위가 주어집니다. 해야 할 작업은 먼저 해당 숫자의 이진수 표현을 구한 다음, 왼쪽 비트부터 오른쪽 비트까지 차례대로 확인하면서 주어진 범위 안에 포함된 설정되지 않은 비트(unset bit)의 개수를 세는 것입니다.
이진수에서 설정되지 않은 비트(unset bit)는 0으로 표현됩니다. 정숫값을 이진수로 변환하면 0과 1의 조합으로 나타나는데, 컴퓨터 용어로 0에 해당하는 비트를 unset bit라고 부릅니다.
입력·출력 예시
입력 − int number = 50, left = 2, right = 5
출력 − 범위 내 총 unset bit 개수: 2
설명 − 50의 이진수 표현은 110010입니다. left = 2인 비트부터 right = 5인 비트까지의 범위 안에는 두 개의 0이 존재합니다. 따라서 unset bit의 개수는 2입니다.
입력 − int number = 42, left = 1, right = 6
출력 − 범위 내 총 unset bit 개수: 3
설명 − 42의 이진수 표현은 101010입니다. left = 1부터 right = 6까지의 범위 안에는 세 개의 0이 존재합니다. 따라서 unset bit의 개수는 3입니다.
프로그램에서 사용된 접근 방식
- 정수형 변수에 숫자를 입력받고, left와 right 정숫값으로 범위를 함께 입력받습니다.
- 카운트를 저장할 변수 count와 전체 비트 수를 저장할 변수 total_bits를 unsigned int 타입으로 선언합니다.
- i를 1<<7부터 시작해 i > 0일 때까지 i = i / 2로 반복하는 FOR 루프를 시작합니다.
- 루프 내부에서 num & i가 참이면 1을, 거짓이면 0을 출력하여 8비트 이진수를 화면에 표시합니다.
- i를 left부터 right까지 증가시키는 FOR 루프를 시작합니다.
- 루프 내부에서 주어진 범위에 포함된 전체 비트 수(total_bits)를 하나씩 증가시킵니다.
- 숫자가 0이 아닐 때까지 반복하는 WHILE 루프로 숫자의 전체 설정 비트 수를 계산합니다.
- 루프 내부에서 count = count + (number & 1)로 설정 비트를 누적하고, number >>= 1로 오른쪽 시프트합니다.
- 임시 변수 a를 ((1 << right) - 1) ^ ((1 << (left - 1)) - 1)로 설정하여 주어진 범위에 해당하는 비트 마스크를 만듭니다.
- count를 count & a로 갱신하여 범위 내 설정 비트만 남깁니다.
- 마지막으로 count를 '범위 내 전체 비트 수 − 범위 내 설정 비트 수'로 계산하여 unset bit의 개수를 구합니다.
예제 코드
#include<iostream>
using namespace std;
//범위 내 총 unset bit 개수 세기
unsigned int unset_bits(unsigned int number, unsigned int left, unsigned int right){
unsigned int count = 0;
unsigned int total_bits = 0;
unsigned i;
//8비트 이진수 출력
cout<<number<<"의 8비트 표현: ";
for (i = 1 << 7; i > 0; i = i / 2){
(number & i)? cout<<"1": cout<<"0";
}
//주어진 범위의 전체 비트 수 계산
for(i = left; i<=right; i++){
total_bits++;
}
//숫자의 전체 설정 비트 수 계산
while (number){
count += number & 1;
number >>= 1;
}
//범위에 해당하는 비트 마스크 계산
int a = ((1 << right) - 1) ^ ((1 << (left - 1)) - 1);
count = count & a;
//범위 내 전체 비트 수에서 설정 비트 수를 뺌
count = total_bits - count;
cout<<"\n범위 내 총 unset bit 개수: "<<count;
}
int main(){
unsigned int number = 80;
unsigned int left = 1, right = 4;
unset_bits(number, left, right);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
80의 8비트 표현: 01010000 범위 내 총 unset bit 개수: 2