문제 개요
정수 num이 입력으로 주어졌을 때, C++의 bitset을 사용하여 해당 숫자의 이진 표현에서 뒤쪽에 연속해서 나오는 0(후행 0, trailing zeroes)의 개수를 구하는 것이 목표입니다.
bitset은 0과 1의 비트 값을 저장하는 자료구조로, 하나의 비트 배열처럼 동작합니다. 각 비트에 인덱스로 접근할 수 있어 이진수 관련 문제를 손쉽게 처리할 수 있습니다.
예제
입력
num = 10
출력
Bitset을 사용한 이진 표현의 후행 0 개수: 1
설명
10을 이진수로 표현하면 1010이므로, 뒤에 붙어 있는 0은 1개입니다.
입력
num = 64
출력
Bitset을 사용한 이진 표현의 후행 0 개수: 6
설명
64는 2의 6제곱이므로 이진수로 1000000으로 표현되며, 후행 0은 6개입니다.
풀이 접근 방법
이 문제는 bitset의 비트 단위 연산과 인덱스 접근 기능을 활용하여 해결할 수 있습니다. 숫자를 bitset에 저장한 뒤, 가장 낮은 자리 비트(LSB)부터 차례대로 검사하여 처음으로 1이 등장하기 전까지의 0의 개수를 세는 방식입니다.
정수
num을 입력받습니다.trailing_zeroes(int num)함수는num을 받아 bitset을 사용해 이진 표현의 후행 0 개수를 계산하여 반환합니다.카운트 변수
count를 0으로 초기화합니다.64비트 크기의 bitset
arr을 선언합니다.arr |= num;연산으로num의 비트 값을 bitset에 설정합니다.i = 0부터i < 64까지 for 루프로 bitset을 순회하면서,arr[i]가 0이면count를 증가시키고, 1을 만나면 즉시 루프를 종료합니다.루프가 끝나면
count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int trailing_zeroes(int num){
int count = 0;
bitset<64> arr;
arr |= num;
for (int i = 0; i < 64; i++){
if (arr[i] == 0){
count++;
} else {
break;
}
}
return count;
}
int main(){
int num = 6;
cout<<"Bitset을 사용한 이진 표현의 후행 0 개수: "<<trailing_zeroes(num);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Bitset을 사용한 이진 표현의 후행 0 개수: 1
입력값 6은 이진수로 110이므로, 후행 0이 1개인 것을 확인할 수 있습니다. 이처럼 bitset을 사용하면 별도의 시프트 연산 없이도 인덱스만으로 각 비트를 검사할 수 있어 코드가 간결하고 직관적이라는 장점이 있습니다.