32비트 부호 없는(unsigned) 이진수가 주어졌을 때, 그 안에 포함된 세트 비트(set bit), 즉 값이 '1'인 비트의 개수를 세는 것이 이번 문제의 목표입니다.
문제 예시
입력:
N = 00000000000000100111
출력:
4
설명: 주어진 부호 없는 수에는 세트 비트가 총 4개 있으므로, 결과값으로 '4'를 반환합니다.
문제 해결 접근 방법
부호 없는 32비트 이진수가 주어지고, 이 수 안에 '1'이 몇 개 들어 있는지 세야 합니다.
'1'의 개수를 세는 가장 간단한 방법은 비트를 일일이 검사하는 대신, 컴파일러나 표준 라이브러리가 제공하는 내장 기능을 활용하는 것입니다. 대표적인 방법은 다음과 같습니다.
- __builtin_popcount(n): GCC 계열 컴파일러에서 제공하는 내장 함수로, 정수 n을 매개변수로 받아 세트 비트의 개수를 반환합니다.
- bitset<32>(n).count(): n을 32비트 bitset 객체로 변환한 뒤, count() 멤버 함수로 '1'의 개수를 얻습니다.
- std::popcount(n) (C++20 이상): 표준 라이브러리에 새로 추가된 함수로, 컴파일러 확장 없이 세트 비트 개수를 구할 수 있습니다.
전체적인 풀이 흐름은 다음과 같습니다.
- 이진수 N을 입력으로 받습니다.
- count1bits(uint32_t n) 함수가 32비트 이진수를 입력받아 그 안의 '1' 개수를 반환합니다.
- 내장 함수가 n을 매개변수로 받아 개수를 계산하고, 그 결과를 출력합니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int count1bits(uint32_t n) {
return bitset<32>(n).count();
}
int main() {
// C++14부터 지원되는 2진수 리터럴(0b) 사용
uint32_t N = 0b0000000010100000011;
cout << count1bits(N) << endl;
return 0;
}
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력
4
입력된 수에는 세트 비트, 즉 '1'이 4개 포함되어 있으므로 출력은 '4'입니다.
코드 설명
bitset<32>(n)은 정수 n을 32비트 크기의 bitset 객체로 변환하며, count() 함수는 그중 값이 1인 비트의 개수를 상수 시간 O(1)에 반환합니다. GCC 환경이라면 return 문을 __builtin_popcount(n)으로 바꿔도 동일한 결과를 얻을 수 있습니다.
참고: 2진수 리터럴 작성 시 주의 사항
C++에서 맨 앞에 0이 붙은 정수 리터럴은 8진수로 해석됩니다. 따라서 0000000010100000011처럼 0으로 시작하는 값을 그대로 코드에 넣으면 의도한 2진수 값과 전혀 다른 수가 되어 버립니다. C++14 이상에서는 0b 접두사를 붙여 0b0000000010100000011과 같이 작성해야 의도한 2진수 그대로 처리됩니다.
대안: 브라이언 커니핸 알고리즘
내장 함수를 사용할 수 없는 환경이라면, n & (n-1) 연산을 반복하는 브라이언 커니핸(Brian Kernighan) 알고리즘을 활용할 수 있습니다. 이 방식은 세트 비트 개수만큼만 반복하므로 매우 효율적입니다.
int count1bits(uint32_t n) {
int count = 0;
while (n) {
n &= (n - 1); // 가장 오른쪽의 1비트 제거
count++;
}
return count;
}